Abstract
We describe in this article how we have been able to extend the record for computations of discrete logarithm sin characteristic 2 from the previous record over \( \mathbb{F}_{2^{503} } \) to a newer mark of \( \mathbb{F}_{2^{607} } \) , using Coppersmith’s algorithm. This has been made possible by several practical improvements to the algorithm. Although the computations have been carried out on fairly standard hardware, our opinion is that we are nearing the current limits of the manageable sizes for this algorithm, and that going substantially further will require deeper improvements to the method.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
L. M. Adleman. A subexponential algorithm for the discrete logarithm problem with applicationsto cryptography. In Proc. 20th FOCS, pp. 55–60. IEEE, 1979.
L. M. Adleman. The function field sieve. In L. Adleman and M.-D. Huang, eds., ANTS-I, vol. 877 of Lecture Notes in Comput. Sci., pp. 108–121. Springer-Verlag, 1994. Proc. 1st Algorithmic Number Theory Symposium, Cornell University, May 6–9, 1994.
L. M. Adleman and J. DeMarrais. A subexponential algorithm for discrete logarithmso ver all finite fields. Math. Comp., 61(203):1–15, July 1993.
S. Arita. Algorithmsfor computationsin Jacobiansof Cab curve and their application to discrete-log-based public key cryptosystems. In Proceedings of Conference on The Mathematics of Public Key Cryptography, Toronto, June 12–17, 1999.
I. F. Blake, R. Fuji-Hara, R. C. Mullin, and S. A. Vanstone. Computing logarithms in finite fieldsof characteristic two. SIAM J. Alg. Disc. Meth., 5(2):276–285, June 1984.
CABAL. Factorization of RSA-140 using the number field sieve. Available online at ftp://ftp.cwi.nl/pub/herman/NFSrecords/RSA-140, Feb. 1999.
CABAL. 233-digit SNFS factorization. Available online at ftp://ftp.cwi.nl/pub/herman/SNFSrecords/SNFS-233, Nov. 2000.
S. Cavallar. Strategies in filtering in the number field sieve. In W. Bosma, ed., Proc. ANTS-IV, vol. 1838 of Lecture Notes in Comput. Sci., pp. 209–231. Springer-Verlag, 2000.
S. Cavallar et al. Factorization of a 512-bit RSA modulus. In B. Preneel, ed., Proc. EUROCRYPT 2000, vol. 1807 of Lecture Notes in Comput. Sci., pp. 1–18. Springer-Verlag, 2000.
F. Chabaud and R. Lercier. ZEN, a toolbox for fast computation in finite extensions over finite rings. Homepage at http://www.di.ens.fr/~zen.
D. Coppersmith. Fast evaluation of logarithms in fields of characteristic two. IEEE Trans. Inform. Theory, IT-30(4):587–594, July 1984.
D. Coppersmith. Solving linear equations over GF(2) via block Wiedemann algorithm. Math. Comp., 62(205):333–350, Jan. 1994.
T. Denny and V. Müller. On the reduction of composed relations from the number field sieve. In H. Cohen, ed., Proc. ANTS-II, vol. 1122 of Lecture Notes in Comput. Sci., pp. 75–90. Springer-Verlag, 1996.
W. Diffie and M. E. Hellman. New directionsin cryptography. IEEE Trans. Inform. Theory, IT-22(6):644–654, Nov. 1976.
B. Dodson and A. K. Lenstra. NFS with four large primes: an explosive experiment. In D. Coppersmith, ed., Proc. CRYPTO’ 95, vol. 963 of Lecture Notes in Comput. Sci., pp. 372–385. Springer-Verlag, 1995.
T. ElGamal. A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inform. Theory, IT-31(4):469–472, July 1985.
G. Frey and H.-G. Rück. A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comp., 62(206):865–874, Apr. 1994.
S. D. Galbraith, S. M. Paulus, and N. P. Smart. Arithmetic on superelliptic curves. To appear in Mathematics of Computation, 2001.
D. M. Gordon. Discrete logarithms in GF(p) using the number field sieve. SIAM J. Discrete Math., 6(1):124–138, Feb. 1993.
D. M. Gordon and K. S. McCurley. Massively parallel computation of discrete logarithms. In E. F. Brickell, ed., Proc. CRYPTO’ 92, vol. 740 of Lecture Notes in Comput. Sci., pp. 312–323. Springer-Verlag, 1993.
T. Granlund. GMP, the GNU multiple precision arithmetic library. Homepage at http://www.swox.se/gmp.
A. Joux and R. Lercier. Discrete logarithms in GF(p) (120 decimal digits). Email to the NMBRTHRY mailing list; available at http://listserv.nodak.edu/archives/nmbrthry.html, Apr. 2001.
A. Joux and R. Lercier. Discrete logarithms in GF(2n) (521 bits). Email to the NMBRTHRY mailing list; available at http://listserv.nodak.edu/archives/nmbrthry.html, Sept. 2001.
E. Kaltofen. Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems. Math. Comp., 64(210):777–806, July 1995.
E. Kaltofen and A. Lobo. Distributed matrix-free solution of large sparse linear systems over finite fields. Algorithmica, 24:331–348, 1999.
N. Koblitz. Elliptic curve cryptosystems. Math. Comp., 48(177):203–209, Jan. 1987.
N. Koblitz. Hyperelliptic cryptosystems. J. of Cryptology, 1:139–150, 1989.
B. A. LaMacchia and A. M. Odlyzko. Solving large sparse linear systems over finite fields. In A. J. Menezes and S. A. Vanstone, eds., Proc. CRYPTO’ 90, vol. 537 of Lecture Notes in Comput. Sci., pp. 109–133. Springer-Verlag, 1990.
A. K. Lenstra and H. W. Lenstra, Jr., eds. The development of the number field sieve, vol. 1554 of Lecture Notes in Math. Springer, 1993.
A. K. Lenstra and M. S. Manasse. Factoring with two large primes. Math. Comp., 63(208):785–798, Oct. 1994.
R. Lidl and H. Niederreiter. Finite fields. Number 20 in Encyclopedia of mathematics and its applications. Addison-Wesley, Reading, MA, 1983.
A. Menezes, T. Okamoto, and S. A. Vanstone. Reducing elliptic curves logarithms to logarithmsin a finite field. IEEE Trans. Inform. Theory, IT-39(5):1639–1646, Sept. 1993.
A. J. Menezes. Elliptic curve public key cryptosystems. Kluwer Academic Publishers, 1993.
P. L. Montgomery. A block Lanczosalgorithm for finding dependencieso ver GF(2). In L. C. Guillou and J.-J. Quisquater, eds., Proc. EUROCRYPT’ 95, vol. 921 of Lecture Notes in Comput. Sci., pp. 106–120, 1995.
H. Niederreiter. A new efficient factorization algorithm for polynomialso ver small finite fields. Appl. Algebra Engrg. Comm. Comput., 4:81–87, 1993.
A. M. Odlyzko. Discrete logarithmsin finite fieldsand their cryptographic significance. In T. Beth, N. Cot, and I. Ingemarsson, eds., Proc. EUROCRYPT’ 84, vol. 209 of Lecture Notes in Comput. Sci., pp. 224–314. Springer-Verlag, 1985.
C. Pomerance and J. W. Smith. Reduction of huge, sparse matrices over finite fields via created catastrophes. Experiment. Math., 1(2):89–94, 1992.
C. P. Schnorr. Efficient signature generation by smart cards. J. of Cryptology, 4(3):161–174, 1991.
E. Thomé. Fast computation of linear generators for matrix sequences and application to the block wiedemann algorithm. In B. Mourrain, ed., Proc. ISSAC’ 2001, pp. 323–331. ACM Press, 2001.
G. Villard. A study of Coppersmith’s block Wiedemann algorithm using matrix polynomials. Research Report 975, LMC-IMAG, Grenoble, France, Apr. 1997.
G. Villard. Further analysis of Coppersmith’s block Wiedemann algorithm for the solution of sparse linear systems. In W. W. Küchlin, ed., Proc. ISSAC’ 97, pp. 32–39. ACM Press, 1997.
D. Weber and T. Denny. The solution of McCurley’s discrete log challenge. In H. Krawczyk, ed., Proc. CRYPTO’ 98, vol. 1462 of Lecture Notes in Comput. Sci., pp. 458–471. Springer-Verlag, 1998.
D. H. Wiedemann. Solving sparse linear equations over finite fields. IEEE Trans. Inform. Theory, IT-32(1):54–62, Jan. 1986.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Thomé, E. (2001). Computation of Discrete Logarithms in \( \mathbb{F}_{2^{607} } \) . In: Boyd, C. (eds) Advances in Cryptology — ASIACRYPT 2001. ASIACRYPT 2001. Lecture Notes in Computer Science, vol 2248. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45682-1_7
Download citation
DOI: https://doi.org/10.1007/3-540-45682-1_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42987-6
Online ISBN: 978-3-540-45682-7
eBook Packages: Springer Book Archive