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 $latex GF(p^{47})$ with $latex 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 + 4750967The 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 32x16 cores.We thus obteined logarithms for linear polynomials.
For instance,
Log(t-1) =
95827955417372788961211119750729924268406734418129865124327290943031748139633075856081325136909045486230487619158973618846263919909919150212528157434853712325214875504194789523385391155086793943715663752308942079859114910805192726927916119880113567931724180868901724860373253630442936157531712330314891742481658155699597613
(mod C)log(t-2) =
70905284732380959516896012578102147920229391687071272347471391289380170629739287997848344272408632657718653331501828887867364669182344802079044434461762058103438602580032253383337456432724367688154096671950400184075089994517877672779201601421554905236313618024147453867620526117100039277887621947094730742958277464818390465
(mod C)log(t+1) =
22191972958014792087327587759372999165298380738905775861595551751866959362993296125893211952064352555004446612143691021766646405907481542823844552325603659164668672726530544973918734915538721151817523682923173974904494997472327204905307992934306560207700268824803542475788420305869403355275251219067807853032669466128535944log(u-1) =
10001005486471873053960223144281754249953393197014591659906662835754390574748823006781373757701566144563328082608672337798845376273684215346619102506040911370085228108583424360298236711416252784630124891603397593416751070128068071222671809409993310027600177764254738174863646977658739191171546816174310362854136358144609763log(u-2) =
61527690212720714271643822401094097115568720581734405966071391248119069776122647831131972276710437710284864058161818513299199927610900547501499496582171428217613040720230663796340038830052388536847031906010338335587455060078065171347461120964945190720689474052263809706188924679921054683415735227928798768439809316649275349
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),
References:
===========[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/