Gröbner bases for nubbies Revisiting Berlekamp's problem Polynomial systems arising from a Weil descent The Successive Resultant Algorithm (SRA) Applications and Perspectives Related papers and talks
Linear systems of equations can be solved efficiently with the Gaussian elimination algorithm. Polynomial systems, on the other hand, are much harder to solve. In a sense, Gröbner bases are to polynomial systems what triangular matrices are to linear systems. Given a Gröbner basis of a polynomial system for the lexicographic ordering, the system can be solved efficiently "one variable at the time". The problem of solving polynomial systems is then reduced to the problem of computing a Gröbner basis for the lexicographic ordering. Gröbner bases algorithms usually compute a Gröbner basis of the system for the degree reverse lexicographic ordering and then convert that basis to a lexicographic Gröbner basis using the [FGLM] algorithm. The first part reduces to linear algebra [L83]. Polynomial multiples of the original equations are added to the system. When sufficiently many equations are added, each monomial term is seen as an independent variable and the system is solved with linear algebra. Sophisticated Gröbner bases algorithms exploit parallelism and choose the new equations carefully to avoid linear dependencies [F4,F5]. In general, solving a system of polynomial equations takes a time exponential in the total degree (the sum of the degrees). However, systems arising in cryptography tend to be nothing but generic. The additional structure they have compared to generic systems will usually make them easier to solve. Additional information on Gröbner basis and some cryptanalysis applications can be found at Jean-Charles Faugère's homepage, arguably the world's expert in the field. One problem I very actively contributed to is a variant of Berlekamp's problem.Revisiting Berlekamp's problem
Let f be a univariate polynomial over a finite field F(q). In a now famous paper, Berlekamp showed how to solve the equation f(x)=0 [B70]. Let now f be a multivariate polynomial equation. The equation f(x1,...,xN)=0 is expected to have a lot of solutions for "random" f. To compute one solution, we can simply fix all variables but the first one randomly and then apply Berlekamp's algorithm. Now suppose q=p^n for a "small" prime p and a "large" integer n. The field F(p^n) is a vector space over F(p). Let Vi be N vector subspaces of F(p^n) of dimension n' roughly n/N. Then the equationPolynomial systems arising from a Weil descent
This problem can be solved as follows. Substitute each variable xi over F(p^n) by n' variables xij over F(p). Choose a basis of F(p^n) over F(p). Decomposing f with respect to that basis, we obtain n polynomial equations in n'N variables. A natural approach to solve that system is to use Gröbner basis algorithms. If the system was generic, solving it would require a time exponential in the total degree of the system, that is bounded by nNt if the degree of f is bounded by p^t in each variable. However, experimental evidence and theoretical arguments show that the system constructed in this way is much easier to solve than a generic system would be. In fact, it appears that the problem can be solved in time (n')^(omega*D), where omega is the linear algebra constant andThe Successive Resultant Algorithm (SRA)
When f is a monovariate polynomial, Berlekamp's trace algorithm (BTA) can compute its roots with a complexity that is much better than suggested by the bounds obtained using a Weil descent and Gröbner basis algorithms. Could we generalize BTA to the more general problem described above ?