From dweber@cs.uni-sb.deWed Sep 25 23:39:12 1996 Date: Wed, 25 Sep 1996 09:35:17 -0400 From: Damian Weber To: NMBRTHRY@listserv.nodak.edu Subject: discrete log Discrete logarithms mod p 23.09.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 [8], [1]. We now solved 59^x = 29 mod p, 59^y = 53 mod p, p=310819380804196114121911120519682610196601011964030919711805194127121970060719 1207059 (85 decimal digits, 281 bits) with q:=(p-1)/2 prime. x=305103203981097657544750529083480525598523318926602209653132252442978494499067 6327395 mod p-1 y=124452612734487844896460352377680630385775290491895908124979750070400316923366 1409571 mod p-1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - We chose two quadratic polynomials f(X)=12088651913597925810*X^2+905452079113038068089*X+8749043915900881108603 g(X)=1146890895334804811*X^2+5297984501155169639345*X-3247049136460419754715 with common root m=900324066150081045760591947783901178451104941777707468193881618077848960434289 779843 mod p The factor bases were of size 35346 and 34995 respectively. The sieving procedure was done on 100 workstations using their idle time of 44.5 mips years. The computation was distributed among them by the Library for Parallel Systems (LiPS), which was developed by our research group. Computing 10 dependencies among the rows of the 175046 X 70342 linear system mod q was done by the following steps: - a compactification step, which resulted in a 54866 X 54856 system - the Lanczos algorithm on the parallel PARAGON machine at the KFA in Juelich/Germany within 64 hours on 64 nodes. Due to the compactification step, the computing time for the linear algebra step was reduced by more than 30%. 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. On the Paragon we use A.K. Lenstra's multiprecision package LIP. ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- [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] Marije Elkenbracht-Huizing, A Multiple Polynomial General Number Field Sieve, Algorithmic Number Theory Symposium II (ANTS II), 1996 [3] H.W. Lenstra, A.K. Lenstra, The development of the number field sieve, Springer 1993 [4] Dan Gordon, Discrete Logarithms in GF(p) using the Number Field Sieve, SIAM J. Discrete Math., Vol 6 (1993) pp. 124-138 [5] Oliver Schirokauer, Discrete Logarithms and Local Units, Phil. Trans. R. Soc. Lond. A 345, 409--423, 1993 [6] Oliver Schirokauer, Damian Weber, Thomas F. Denny, Discrete Logarithms: the Effectiveness of the Index Calculus Method, Algorithmic Number Theory Symposium II (ANTS II), 1996 [7] 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 [8] Damian Weber, Computing Discrete Logarithms with the Number Field Sieve, Algorithmic Number Theory Symposium II (ANTS II), 1996 [9] 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: 'j.zayer@ids-scheer.de') * * * * Research group of Johannes Buchmann * * Universitaet des Saarlandes / Tech. Hochschule Darmstadt * * * ********************************************************************