```Date: Wed, 9 Nov 2005 15:12:44 -0500 Reply-To: Antoine Joux Sender: Number Theory List From: Antoine Joux Subject: Discrete logarithms in GF(370801^30) -- 168 digits -- 556 bits Wednesday, November 9th, 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(370801^30). This was done in less than 12 hours on a 1.15 GHz 16-processors HP AlphaServer GS1280. The approach is a our variation on Adleman's function field sieve [Ad94], announced in [JoLe05], about which we are currently preparing a paper. 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 computations were performed, first by Vercauteren and Lercier [LeVe05] (using the approach of torus representation introduced by Granger and Vercauteren in [GrVe05]), then by Joux and Lercier [JoLe05] (using this new variation of the function field sieve). Precisely, let p = 370801, GF(p^30) = GF(p)[t]/(t^30-17) and g = t - 6. Let pi(t) = sum(i=0,29,(floor(Pi*p^(i+1))%p)*x^i) # GP/PARI syntax = 162147*t^29 + 338795*t^28 + 245060*t^27 + 323878*t^26 + 256820*t^25 + 63079*t^24 + 113985*t^23 + 210740*t^22 + 130675*t^21 + 97042*t^20 + 314407*t^19 + 352378*t^18 + 335134*t^17 + 342280*t^16 + 61106*t^15 + 272171*t^14 + 163784*t^13 + 240850*t^12 + 66741*t^11 + 265046*t^10 + 208274*t^9 + 275057*t^8 + 179507*t^7 + 229391*t^6 + 164345*t^5 + 198249*t^4 + 3434*t^3 + 341005*t^2 + 258649*t + 52502. Then, pi(t) = g^834934758318669039584738321669880646445961989720307919272366432\ 574478787876554087500076043934132539884636443251840515509803922\ 37533812685076653542562214928407573371226 Sieving: -------- We define our algebraic function fields by f_1(X,t)=X-t^5 and f_2(X,t)=X^6+X-17-t^5 and our smoothness basis contain places of degree 1. We further use the fact that the reduction modulo p of these places are conjugates each other by the Galois action given by t->t^(p^6)=213181*t, we finally had to deal with only 148275 degree one places. In this setting, our sieving software found 329082 useful divisors of the form \$Div X-(at+b)\$ with \$a\$ and \$b\$ in \$\GF{p}\$, at the cost of a 45 minutes computation. Linear algebra: --------------- We modified our implementation of the Lanczos algorithm to deal with this case and we were finally able to solve a sparse system of 150270 equations in 148270 variables (11 entries by row equal to \$p^{6i}\$, \$i=0,\ldots 4\$) at the cost of a 10 hours computation on 8 processors of a 1.15 GHz HP AlphaServer GS1280. We worked modulo Q = 129717983265199170691 * 3780896193379818021601 * 27084969683231313608318791573698901. To check these logarithms, we make use of G=g^((p^30-1)/Q). For instance, (t-1)^((p^30-1)/Q)= G^858814752732049131584663651366411191299849888095646311187\ 1919059262793471473 and (t^5+t-1)^((p^30-1)/Q)= G^540446525581805802972783150755982258918174413208848454470\ 7050634558305662620 Individual Logarithms: ---------------------- We found in a few minutes two polynomials, num(t) = (t + 55564) * (t + 128273) * (t + 320783) * (t^2 + 67030 * t + 124516) * (t^2 + 141998 * t + 97806) * (t^2 + 230077 * t + 272221) * (t^3 + 281540 * t^2 + 359570 * t + 326930) * (t^3 + 283548 * t^2 + 45715 * t + 97297) and den(t) = (t + 20273) * (t + 118843) * (t + 187495) * (t + 223094) * (t + 334013) * (t^2 + 4164 * t + 141667) * (t^2 + 16050 * t + 165737) * (t^2 + 343958 * t + 368575) * (t^4 + 128873 * t^3 + 108876 * t^2 + 126230 * t + 114295) such that pi(t) = 33389 * num(t) / den(t) in GF(p^30). Then, using special-q descents, we concluded the computation in 40 minutes of CPU-time. So, as a conclusion, computing discrete logarithms in GF(370801^30) using the function field sieve can be done very efficiently using a total slightly less than 0.5 days on a 1.15 GHz HP AlphaServer GS1280. 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 [JoLe05] A. Joux and R. Lercier, ``Discrete logarithms in GF(65537^25) -- 120 digits -- 400 bits'', NMBRTHRY list, October, 2005 ```