Dear Number Theorists, We are pleased to announce a new computation of a discrete logarithm in a finite field whose order has 160 digits and is a degree 2 extension of a prime field. The algorithm used was the number field sieve (NFS), with various modifications. The total computing time was equivalent to 68 days on one core of CPU (sieving) and 30 hours on a GPU (linear algebra). To our knowledge, this kind of computation has not be reported before, but for reference, we recall that until the recent announcement of 180 digits, the record for discrete log computation in a prime field was also of 160 digits. The 80-digit prime p was chosen from the decimal digits of pi, such that both p-1 and p+1 have a large prime factor. We also forced p to be 7 modulo 8, so that we could use our favorite cyclotomic polynomial (see below), but other congruences modulo 8 can be tackled in about the same running time. p = 3141592653589793238462643383279502884197\ 1693993751058209749445923078164063079607 Computing logarithms modulo p-1 raises no particular difficulty, and we concentrated on the logarithms modulo the following prime divisor of p+1: ell = 3926990816987241548078304229099378605246\ 461749218882276218680740384770507884951 The defining polynomial of GF(p^2) over GF(p) was chosen to be: phi = t^2 + 8827843659566562900817004173601064660843\ 646662444652921581289174137495040966990*t + 1 and we used g = t + 2 as a generator. The logarithm in base g of the following "random" element: s = Floor(Pi*(2^264)/4)*t + Floor(EulerGamma*2^264) is then log(s) = 4317246464747174995321414320990695178326\ 07980262114471597315861099398586114668 modulo ell. Verification scripts are provided at the end of the message. Details on the computation: =========================== Most of the computation uses software that is freely available: - CADO-NFS [1] for the sieving, filtering, and most of the individual logarithms; - Jeljeli's GPU linear algebra package [2]. Polynomial selection: --------------------- For this step, we used a new technique that provides smaller sizes than the method by Joux, Lercier, Smart and Vercauteren [3]. Moreover the two polynomials are chosen with nice properties so that speed-up are possible at different stages. This computation takes essentially no time. We used f = x^4 + 1 g = 22253888644283440595423136557267278406930*x^2 + 41388856349384521065766679356490536297931*x + 22253888644283440595423136557267278406930. Note that both polynomials are reciprocal, and that g has negative discriminant. Relation collection: -------------------- We used the lattice sieving software of CADO-NFS for this step. Prime ideals on both sides that are below 40M were sieved and we allowed 2 large primes less than 2^27 on each side. We sieved over special-q's on the g-side between 40M and 60M. The sieving generated 15M relations and took around 68 core-days (2-GHz Intel E5-2650). Due to the reciprocal polynomials, we sieved only half of the special-q in the target range. Filtering: ---------- The filtering step was run as usual, but we modified it to take into account the Galois action on the ideals: we selected a representative ideal in each orbit under the action $x \mapsto x^{-1}$, and rewrote all the relations in terms of these representatives only. The output of the filtering step was a matrix with 839,244 rows and columns, having on average 83.6 non-zero entries per row. Due to number field properties, it was not necessary to add columns with Schirokauer maps. Linear algebra: --------------- We used Jeljeli's implementation of Block Wiedemann's algorithm for GPUs. In fact, this was a small enough computation so that we did not distribute it on several cards: we used a non-blocked version. The total running time for this step was around 30.3 hours on an NVidia GTX 680 graphic card. At the end of the linear algebra we know the virtual logarithms of almost all prime ideals of degree one above primes of at most 26 bits, and of some of those above primes of 27 bits. At this point we could test that the logs on the f-side were correct. Individual logarithm stage: --------------------------- We started by looking for an integer e such that z = s^e, seen as an element of the number field of f, is smooth. After a few core-hours, we found a value of e such that z = z1/z2 with z1 and z2 splitting completely into prime ideals of at most 60 bits. With the lattice-sieving software of CADO-NFS, we then performed a "special-q descent" for each of these prime ideals. We remark that one of the prime ideals in z1 was an ideal of degree 2 above 43, that had to be descended in a specific way, starting with a polynomial of degree 2 instead of 1. The total time for descending all the prime ideals was a few minutes. Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic, François Morain References: =========== [1] S. Bai, C. Bouvier, A. Filbois, P. Gaudry, L. Imbert, A. Kruppa, F. Morain, E. Thomé and P. Zimmermann. CADO-NFS. http://cado-nfs.gforge.inria.fr/ [2] H. Jeljeli. An implementation of the Block-Wiedemann algorithm on NVIDIA-GPUs using the Residue Number System (RNS) arithmetic. Available from http://www.loria.fr/~hjeljeli/ [3] A. Joux, R. Lercier, N. Smart, F. Vercauteren. The number field sieve in the medium prime case. CRYPTO 2006, LNCS 4117, p. 326-344, Springer. Verification scripts: ===================== Magma script: ------------- p := 31415926535897932384626433832795028841971693993751058209749445923078164063079607; ell := 3926990816987241548078304229099378605246461749218882276218680740384770507884951; h := (p^2-1) div ell; varphi:=Polynomial([GF(p) | 1,8827843659566562900817004173601064660843646662444652921581289174137495040966990,1]); Fpn:=ext; gen := t + 2; R:=RealField(280); s1:=Floor(Pi(R)*2^264/4); s0:=Floor(EulerGamma(R)*2^264); target:=s1*t + s0; log_target := 431724646474717499532141432099069517832607980262114471597315861099398586114668; assert target^h eq gen^(h*log_target); Sage script: ------------ p = 31415926535897932384626433832795028841971693993751058209749445923078164063079607 ell = 3926990816987241548078304229099378605246461749218882276218680740384770507884951 h = (p^2-1) // ell varphi=GF(p)['x'] ([ 1,8827843659566562900817004173601064660843646662444652921581289174137495040966990,1]) Fpn.=GF(p^2,modulus=varphi); gen = t + 2 target = 23281380921073044753935036337774711209817176149017115517361417671548089245835857*t + 17110273991540504259863674318281574234623888530768743939507283540597018487405966 log_target = 431724646474717499532141432099069517832607980262114471597315861099398586114668 assert target^h == gen^(h*log_target)