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 *
********************************************************************
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -