Discrete logarithms mod p ========================= We announce a new record concerning the discrete logarithm problem in Fp achieved with our implementation of the ideas of Dan Gordon and Oliver Schirokauer about the usage of the general number field sieve algorithm. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - We solved 7^x = b mod p, b in {2,3,5,11,13,17,19,23,29} where p is the 65-digit number (215 bits) 31081938120519680804196101011964261019661412191103091971180537759. p-1=2*q, q prime q=15540969060259840402098050505982130509830706095551545985590268879. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - We used the polynomial f(X)=-57969887*X^4 -1040988700418*X^3 -1599410033377*X^2 +2467898905167*X +2804774217242 The primes of both factor bases are the first-degree primes with norm less than 27449 (rational), 187951 (algebraic). The sieving interval for c+dm, c+d@ was chosen as follows -4000000 < c < 4000000 0 < d < 500000. The sieving procedure was done on 130 workstations using their idle time of 5 y 116 d 15 h 36 m (mips). The computation was distributed among them with the Library for Parallel Systems (LiPS), which was developed by our research group. The solution of the 20442 X 19957 linear system mod q was done on a Paragon machine at the KFA in Juelich/Germany within 38 hours on 50 nodes by using the Lanczos algorithm. The solution of x mod 2 was easily to obtain by using the Pohlig-Hellman algorithm. In the final step we had to combine the results using the Chinese- Remainder-Theorem - this lead to 7^12947465376923824724957499951503053332437571430268512704320339344= 2 mod p 7^22080187724931255875760876853515374478171170414218024970175409792= 3 mod p 7^9020360122054471637752764322421325610990892645529499177414056196 = 5 mod p 7^9945551073244673320177388140562285016902916888328194474544106942 =11 mod p 7^15156730731943267081963372032905052327723905195485355154769047594=13 mod p 7^8152659639161629852616660237224454396691805969032182443520670007 =17 mod p 7^8429438942722042183611304520083018385242987760831227887869827458 =19 mod p 7^29153020481930701437148309607402611581505734463034646141828747593=23 mod p 7^22997906266006136529682973437413418001682127605800489536168728807=29 mod p We used our package for computational algebraic number theory named LiDIA, created by the LiDIA group, which has a multiprecision C-kernel called libI written by Ralf Dentzer, Universitaet Heidelberg. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - The previous record was obtained by solving a DL problem in Fp, where p had 192 bits, (p-1)/2 prime (LaMacchia/Odlyzko). ******************************************************************** * Damian Weber (email: 'dweber@cs.uni-sb.de') * * Thomas F. Denny (email: 'denny@cs.uni-sb.de') * * Joerg Zayer (email: 'zayer@cs.uni-sb.de') * * * * Research group of Johannes Buchmann * * Universitaet des Saarlandes * ********************************************************************