The solution of McCurley's discrete log challenge
This paper presents the solution to a challenge made by Kevin McCurley in 1989. McCurley asked for the secret key obtained from the data exchanged by two parties in a Diffie-Hellman key exchange using the finite field of \(p=(739 \cdot 7^{149}-736)/3\) elements. Due to the special nature of the field the authors were able to use a variant of the special number field sieve to solve the challenge. This paper gives a brief summary on the computational task involved. First a discussion on how the original problem of McCurley is reduced to finding logarithms of ``smooth elements in the field of \(p\) elements. Then the choice of field polynomial for the number field sieve is discussed, a degree five polynomial/field was chosen for the rest of the computation. The sieving is then discussed, with some numerical summary data of the effort involved. Finally the linear algebra step is described. The paper gives a large amount of run time data of the overall algorithm. This calculation is particularly impressive and to date is the largest discrete logarithm problem which has been solved. For the entire collection see [Zbl 0895.00067].
- Cocks-Pinch curves of embedding degrees five to eight and optimal ate pairing computation
- Special prime numbers and discrete logs in finite prime fields
- Discrete logarithm problem using index calculus method
- Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method
- Using number fields to compute logarithms in finite fields
- On the cubic sieve method for computing discrete logarithms over prime fields
- Finite field arithmetic in large characteristic for classical and post-quantum cryptography
- Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm
This page was built for publication: The solution of McCurley's discrete log challenge
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4249351)