From dweber@cs.uni-sb.deSat Mar 9 10:17:52 1996 Date: Fri, 8 Mar 1996 16:52:22 EST From: Damian Weber To: Multiple recipients of list NMBRTHRY Subject: discrete log challenge Challenge of Kevin McCurley =========================== Discrete logarithms mod p ------------------------- 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]. Kevin McCurley published a challenge problem in his 1990 paper "The Discrete Logarithm Problem". The problem is given in form of a Diffie-Hellman-key-exchange communication and can be solved by computing one of the two discrete logarithm problems involved. The prime number he chose is 2*739*q+1, q=(7^149-1)/6 prime. We now solved 7^x = b mod p, for a certain set of small b's. For example 7^79051812480562894353242540763178671604799913001076931312515301149\ 375298305476653734488443974490137127049808298345258246689629965 = 11287 mod p This is only a first step in solving the challenge. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - We used the polynomial f(X)=739X^5-5152 and rational and algebraic factor bases of size 20000 each. The sieving interval for c+dm, c+d@ was chosen as follows -15*10^6 < c < 15*10^6 0 < d < 10^6 The sieving procedure was done on 100 workstations using their idle time of 110 y 262 d 9 h 16 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 40015 X 40000 linear system mod q was done on three Sparc 20 stations within a month by using the Lanczos algorithm. The solution of x mod 2 and mod 739 was easily obtained by using the Pohlig-Hellman algorithm with Pollard-Brent improvement. In the final step we had to combine the results using the Chinese- Remainder-Theorem. 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] H.W. Lenstra, A.K. Lenstra, The development of the number field sieve, Springer 1993 [2] Dan Gordon, Discrete Logarithms in GF(p) using the Number Field Sieve, University of Georgia, preprint, 1992 [3] Oliver Schirokauer, Discrete Logarithms and Local Units, Phil. Trans. R. Soc. Lond. A 345, 409--423, 1993 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ******************************************************************** * 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 * ******************************************************************** - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -