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 with 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 32×16 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/