A new record for the discrete logarithm problem

Recently, a new record for the discrete logarithmic problem was posted in Number Theory mailing list; by recently I mean on 24th Dec. Anyways they were able to compute discrete logarithm in GF(p^{47}) with p=33 553 771 using Kummer Theory. For those who are interested here is the original posting in the list by Antoine Joux

We are pleased to announce a new record for the discrete logarithm
problem. We were able to compute discrete logarithms in
GF(p^47), with p=33,553,771. This was done using a new variation of
the Function Field Sieve for the medium prime case [JoLe06], full details
are given in [Jo12].

As far as we know, the previous discrete logarithm record
in a finite field is GF(3^582), a $923$-bit field [HaShiShiTa12].

We define GF(p^47) using the following Kummer extension
GF(p^47) = GF(p)[t]/(t^47-2)

and we choose as basis for the discrete logarithms, the value:
g = t-3.

We set to ourselves the challenge of computing the logarithm of:
Z=sum(i=0,46,floor(Pi*p^(i+1))%p*t^i) [in Pari-gp syntax]
= 9223132*t^46 + 21572761*t^45 + 13331805*t^44 + 24394461*t^43 +
967257*t^42 + 11418608*t^41 + 22510961*t^40 + 8252042*t^39 +
25554852*t^38 + 26222640*t^37 + 33310861*t^36 + 30299378*t^35 +
12151253*t^34 + 20654171*t^33 + 32174594*t^32 + 944406*t^31 +
779314*t^30 + 31050064*t^29 + 12712559*t^28 + 14346746*t^27 +
22602277*t^26 + 21089035*t^25 + 13665993*t^24 + 9188704*t^23 +
28235615*t^22 + 17237048*t^21 + 10095045*t^20 + 14876208*t^19 +
31889225*t^18 + 2609908*t^17 + 28623908*t^16 + 29096565*t^15 +
13257302*t^14 + 1382226*t^13 + 23604453*t^12 + 12670350*t^11 +
2891114*t^10 + 2125744*t^9 + 2828409*t^8 + 19052742*t^7 +
16935621*t^6 + 14078784*t^5 + 5105395*t^4 + 13487859*t^3 +
31044117*t^2 + 15898925*t + 4750967

The cardinality of the group is:
p^47-1= 47 * 2069 * 12409 * (p-1) * 132103049403319 *C,
where C is a composite cofactor of unknown factorization.
As usual, this computation was done in three steps:
– the generation of multiplication relations,
– the linear algebra,
– the final computation of individual logarithms.

Generation of relations :

Let u=t^6. Then u^8=2t. We see that a polynomial:
ut + a u + b t +c, can be expressed either as a polynomial in t
or a polynomial in u giving a polynomial equality:

t^7 + a t^6 + b t +c = u^9/2 + a u + b u^8/2 +c

When both sides split into linear factors, we obtain a multiplication
relation in GF(p^47) (with a smoothness basis containing all linear
polynomial in t and u). Note that the Frobenius map sends linear
polynomial to linear polynomials, thus reducing the size of the
smoothness basis by a factor 47.

To generate the needed relations, with use a new technique called
pinpointing. The total running time is 3 hours on
a single core of a Intel core i7 at 2.7 GHz.

The structured Gaussian elimination has been merged with the
generation of relations and the resulting linear systems involves
829,405 unknowns
Linear algebra:

The linear algebra used a block Wiedemann approach.

We first performed 32 independent matrix-vector product sequences.
Using 32 machines of 16 cores each, this took 37 hours.

Using Thomé’s approach to block Wiedemann [Thome02], we found a low
degree linear relation between the outputs of the first step in 9h30m on a
64-core machine.

Finally, we recovered a kernel element through another run of 32
matrix-vector product sequences, which took 25 hours on 32×16 cores.

We thus obteined logarithms for linear polynomials.

For instance,

Log(t-1) =
(mod C)

log(t-2) =
(mod C)

log(t+1) =

log(u-1) =

log(u-2) =
Individual Logarithms:

Following the approach from [JoLe06], this phase took under 4 hours on the
Intel laptop. We found that the challenge satisfies:

Z = g ^ 356633127146494066263281134740949440571780807878239530830992112523140494277589347504555481509115749560473147631864963745877949210252568865798642649039047033462050627522813317937084662147227994756376452164608898303687287333791524330937899227952311300252882838173738965961045446180140573240231646914447899262099152488534480737568049333712088197470913054182
Antoine Joux (CryptoExperts and UVSQ, France),

[JoLe06] The Function Field Sieve in the Medium Prime Case. Antoine Joux and
Reynald Lercier. EUROCRYPT’2006

[Thome02] Subquadratic Computation of Vector Generating Polynomials
and Improvement of the Block Wiedemann Algorithm.
Emmanuel Thomé. J. Symb. Comput. 2002 33(5), pp. 757–775

[HaShiShiTa12] Breaking Pairing-Based Cryptosystems Using eta_T Pairing
over GF(3^97). Takuya Hayashi and Takeshi Shimoyama and
Naoyuki Shinohara and Tsuyoshi Takagi. ASIACRYPT’2012.

[Jo12] Faster index calculus for the medium prime case.
Application to a 1175-bit finite field. Antoine Joux. Eprint
Archive. http://eprint.iacr.org/


Published by

Sankalp Ghatpande

Student of MS Information and Computer Science. Interested in Research @ Information Security | Cryptology | Quantum information science.

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