From dweber@cs.uni-sb.deTue Apr 9 16:06:16 1996 Date: Tue, 9 Apr 1996 09:04:20 EDT From: Damian Weber To: Multiple recipients of list NMBRTHRY Subject: DL in prime fields Discrete logarithms mod p 25.03.1996 ------------------------- We announce a new record concerning the discrete logarithm problem in Fp, the finite field of p elements, achieved with our implementation of of the general number field sieve algorithm; for details see [1], [2], [3], [4], [5], [6], [7]. We now solved 5^x = b mod p, b in {2,3,5,7,11,13,17,19}, p=310819381205196808041961141219110101196426101966030919711805194127121999327 (75 decimal digits, 248 bits) with (p-1)/2 prime. 5^247304965037952295066692348548903196491045004838332188604053856130900104778 = 2 mod p 5^9602977964678340753402483392299359891536116663077901343298610781966762006 = 3 mod p 5^147001657721304571107460703308056871315960324818746059568618613166225193632 = 7 mod p 5^253762437654824910964035857039763668258075514706017456372999633994434110941 = 11 mod p 5^204890434527986803740486893000176797293960297959843422287988074270476059103 = 13 mod p 5^99436746918970717034851871806639645816648149055662530185216002220962098391 = 17 mod p 5^304826238078240870953965599601565525277161778098196660032717603407232004336 = 19 mod p - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - We used the polynomial f(X)=41440163*X^4 +8899586579547*X^3 +50013054105621*X^2 -385158712921327*X -226856042090363 rational factor base of size 5000 algebraic factor base of size 20058 The sieving interval for c+dm, c+d@ was chosen as follows -10^7 < c < 10^7 0 < d < 1.2*10^6 The sieving procedure was done on 100 workstations using their idle time of 70 y 16 d 8 h 45 m (mips). The computation was distributed among them by the Library for Parallel Systems (LiPS), which was developed by our research group. The solution of the 25085 X 25070 linear system mod q was done on the parallel PARAGON machine at the KFA in Juelich/Germany within 25 hours on 64 nodes by using the Lanczos algorithm. The solution of x mod 2 was easily obtained by using the Pohlig-Hellman algorithm. Parts of the computation were done by using our package for computational algebraic number theory named LiDIA (http://www-jb.cs.uni-sb.de/LiDIA/linkhtml/lidia/lidia.html) which contains libI as the underlying multiprecision arithmetic written by Ralf Dentzer, Universitaet Heidelberg. [1] Thomas F. Denny, Volker Mueller, On the Reduction of Composed Relations from the Number Field Sieve, Algorithmic Number Theory Symposium II (ANTS II), 1996 [2] H.W. Lenstra, A.K. Lenstra, The development of the number field sieve, Springer 1993 [3] Dan Gordon, Discrete Logarithms in GF(p) using the Number Field Sieve, SIAM J. Discrete Math., Vol 6 (1993) pp. 124-138 [4] Oliver Schirokauer, Discrete Logarithms and Local Units, Phil. Trans. R. Soc. Lond. A 345, 409--423, 1993 [5] Damian Weber, An implementation of the General Number Field Sieve to Compute Discrete Logarithms mod p, Advances in Cryptology - Eurocrypt '95, pp. 95-105, 1995 [6] Damian Weber, Computing Discrete Logarithms with the Number Field Sieve, Algorithmic Number Theory Symposium II (ANTS II), 1996 [7] Joerg Zayer, Faktorisieren mit dem Number Field Sieve, PhD thesis, Saarbruecken, 1995 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ******************************************************************** * 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 * ******************************************************************** - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -