Date:         Mon, 24 Oct 2005 08:34:14 -0400
Reply-To:     Antoine Joux 
Sender:       Number Theory List 
From:         Antoine Joux 
Subject:      Discrete logarithms in GF(65537^25) -- 120 digits -- 400 bits

Monday, October 24th, 2005. We are pleased to announce a new record for the discrete logarithm problem with medium sized base field. We were able to compute discrete logarithms in GF(65537^25). This was done in two days and a few hours on a single Pentium mobile laptop at 1.6 Ghz. The approach is a new variation on Adleman's function field sieve [Ad94], about which we are currently preparing a paper [JoLe05]. From a complexity theoretic point of view, it gives a L(1/3) algorithm in its range of applicability. As the regular function field sieve, it works in three phases, sieving, linear algebra and individual logarithms. As far as we know, the largest previous discrete logarithm computation was performed by Vercauteren and Lercier [LeVe05] using the approach of torus representation introduced by Granger and Vercauteren in [GrVe05]. With this new variation, we could not use our usual sieving code and we wrote a new, independent sieving program. For the linear algebra, we used our usual structured gaussian elimination and Lanczos implementations. Precisely, let p=65537 GF(p^25) = GF(p)[t]/ t^25 + 5*t^21 + 15*t^20 + 10*t^17 + 60*t^16 + 90*t^15 + 10*t^13 + 90*t^12 + 270*t^11 + 270*t^10 + 5*t^9 + 60*t^8 + 270*t^7 + 540*t^6 + 407*t^5 + 15*t^4 + 90*t^3 + 270*t^2 + 407*t + 247 and g = 3*t. Let pi(t) = sum(i=0,24,(floor(Pi*p^(i+1))%p)*x^i) # GP/PARI syntax = 41667*t^24 + 38062*t^23 + 60623*t^22 + 58559*t^21 + 20236*t^20 + 47783*t^19 + 49050*t^18 + 37274*t^17 + 4366*t^16 + 36803*t^15 + 18368*t^14 + 24622*t^13 + 9012*t^12 + 44161*t^11 + 43372*t^10 + 20341*t^9 + 5644*t^8 + 46803*t^7 + 34689*t^6 + 45877*t^5 + 9881*t^4 + 64918*t^3 + 32499*t^2 + 36552*t + 9279. Then, pi(t) = g^405373694505244074458798850727154577337791051707463993575473\ 6348185260902857777282008537164926838353644893694741284146999. Sieving: -------- As usual, the sieving step found multiplicative relations between our smoothness basis elements. The surprising fact is that this phase was extremely fast and only took a couple of minutes to generate the necessary equations. Linear algebra: --------------- The linear algebra was further divided in two phases. We first applied structured Gaussian eliminations to reduce our system to 79466 equations in 78465 unknowns with 3.8 millions non null entries. Then, the bottleneck was the computation via Lanczos's algorithm. Our parallelized version of this algorithm took 2 days on the pentium laptop. At the end, we had logarithms modulo a large factor L of p^25-1 for the elements of our smoothness basis. Here, L=(p^25-1)/((p-1)*3571). To check these logarithms, we make use of G=g^((p-1)*3571). For instance, (t+1)^((p-1)*3571)= G^95805410880093234842298898214533393829434304594545362348\ 24840375483524017353229706334323184929723853320944439485 and (t^5+t+3)^((p-1)*3571)= G^46495712756925209185601240503381083970050573012881700517\ 18556686238431642289730613529631676496393555258546887691. Individual Logarithms: ---------------------- We found in a few minutes two polynomials, num(t) = (t + 20471)*(t + 25396)*(t + 34766)*(t + 54898)* (t^2 + 29819*t + 6546)*(t^2 + 44017*t + 38392)* (t^2 + 54060*t + 4880)*(t^3 + 23811*t^2 + 6384*t + 3243) and den(t) = (t + 18919)*(t + 31146)*(t + 38885)*(t + 53302)* (t^2 + 52365*t + 2605)*(t^3 + 29795*t^2 + 54653*t + 7616)* (12850*t^3 + 35335*t^2 + 14881*t + 36655) such that pi(t) = num(t)/den(t) in GF(p^25). Then, using special-q descents, we concluded the computation in a few minutes of CPU-time. So, as a conclusion, computing discrete logarithms in GF(65537^25) using the function field sieve can be done very efficiently using a total slightly above 2 days on a single laptop. Antoine JOUX (DGA & Universite de Versailles, France, antoine.joux(at)m4x.org), Reynald LERCIER (CELAR, Rennes, France, reynald.lercier(at)m4x.org). References: =========== [Ad94] L.M. Adleman, ``The Function Field Sieve'', ANTS I, Lecture Notes in Math., 1994, volume 877. [GrVe05] R. Granger and F. Vercauteren, ``On the discrete logarithm problem on algebraic tori'', Crypto'05, LNCS 3621. pp 66--85 [JoLe05] A. Joux and R. Lercier, ``The function field sieve in the medium prime case'', In preparation. [LeVe05] R. Lercier and F. Vercauteren, ``Discrete logarithms in GF(p^18) - 101 digits'', NMBRTHRY list, June 28th, 2005