Quasi-polynomial-time algorithm for discrete logarithm in finite fields of small/medium characteristic

A major breakthrough this week has been the announcement by Razvan Barbulescu, Pierrick Gaudry, Antoine Joux and Emmanuel Thomé of a quasi-polynomial-time DLP algorithm for finite fields. The paper is available here

The algorithm applies to finite fields of the form GF( q^k ), where q is a prime power and where q \approx k. We represent this field as GF( q )[x]/(F(x)) where F(x) is an irreducible polynomial of degree k such that F(x) divides h_1(x) x^q - h_0(x), where h_0 and h_1 are linear or quadratic. Since this polynomial has degree q+1 or q+2 it follows that we need k \le q+2.

Following the previous work by Joux (see Section 4), the factor base is the set of linear or quadratic polynomials over GF( q^2 ). First one finds relations among the linear polynomials in polynomial-time O( q^5 ) by substituting into the systematic equation x^q - x = \prod_{a \in GF(q)} (x - a) linear fractional transformations over GF( q^2 ) in x (this is where the group PGL_2( GF( q^2 )) enters; such transformations are also called homographies or Mobius transformations). One gets a cubic polynomial in x equal to a product of linear polynomials. If the cubic polynomial splits (which happens with probability 1/6) then one has a relation. One needs O( q^2 ) such relations. Sparse linear algebra (each row has O( q ) non-zero entries out of O( q^2 )) allows to express the discrete logarithms of linear polynomials with respect to any fixed linear polynomial (x-b) that generates the field. The cost of the linear algebra is O( q^5 ) operations in the ring Z_{q^k-1}.

This is not enough. We also need quadratic polynomials in our factor base. This is explained in Section 4.3 of Joux’s paper. One can handle the issue by solving O( q^2 ) systems of equations (each taking O( q^5 ) operations). Hence, the overall complexity of the first stage is O( q^7 ). This is polynomial time in the input size \log( q^k ) = k \log(q) = q \log(q) (as k \approx q).

The major innovation of the new paper is a new approach for the descent procedure. This is when you take a polynomial P(x), corresponding to the original DLP instance, and want to express it as a product of elements in the factor base. The idea is to recycle ideas from the first step. Suppose \deg(P(x)) = D. One substitutes into the systematic equation a linear fractional transformation x = (a P + b)/(c P + d) over GF( q^2 ). One now has on the left hand side a polynomial in x of degree 3D and on the right hand side a product of linear terms of the form (P - a) for a \in GF( q^2 ). With probability around 1/6! the left hand side splits into a product of polynomials of degree at most D/2. If that happens we have a relation. One needs O( q^2 ) relations and then one can perform linear algebra to eliminate all (P-a) terms on the right hand side, except for P itself. We therefore express P as a product of O( q^2 D ) polynomials of smaller degree (the q^2 term arises as we have combined O( q^2 ) relations, each of which features at most D polynomials).

One then proceeds recursively. Since the degree is initially D=k, but drops from D to D/2 at each stage, there are \log(k) levels of recursion. The total number of polynomials that arise is an enormous (q^2 D)^{O( \log(k) )}. But this is quasi-polynomial in the input size.

And there you have it — surprisingly simple!

Much work will be done to improve the descent step. In practice one will begin with subexponential smoothing as in the function field sieve, then employ both the new method and the Groebner basis method due to Joux.

The method is particularly suitable for fields that can already be written in the form GF( q^k ) with q \approx k. For example, with the recent records GF( 2^{6168} ) we take q = 2^8 = 256, k = 257 and work with GF( q^3 ) instead of GF( q^2 ) for the factor base.

It is interesting to consider the case of prime extensions GF( 2^p ), where p \approx 1000 is prime. The traditional function field sieve would be expected to solve such problems in around 2^{80} to 2^{90} bit operations. For the new approach we need to embed this field into GF( q^k ) with q \approx k. The obvious choice is q = 2^{10}. Then the first stage of the algorithm, as we have mentioned, already takes time proportional to q^7 = 2^{70}. The descent step will be much more time-consuming. For example (q^2 k)^{10} \approx 2^{233}. Of course, we expect this can be improved significantly, but for the moment the new method does not seem to beat FFS for fields of this size (much larger p is another story).

For pairing fields such as GF( 2^{239 * 12} ) = GF( 2^{2868} ) things are much more risky. Taking q = 2^{12} = 4096 and k = 239 is already somewhat close to the ideal range. I would not be surprised if this case is broken before the end of the year.

— Steven Galbraith

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to Quasi-polynomial-time algorithm for discrete logarithm in finite fields of small/medium characteristic

  1. Luca De Feo says:

    Hi Steven,

    You say that a factor base of linear polynomials is not enough, but I can see no mention of this in the BGJT paper. Could you comment more on this?

    • ellipticnews says:

      There was some discussion of this in Paris. Antoine seemed to be of the opinion that linear polynomials are not sufficient, but I am not sure why. I guess that in a few months this will all be more clear, once more computations have been done. I will not be surprised if we eventually can use only linear polynomials, or maybe even fewer (using a “large prime” variation).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s