The number field sieve for integers of low weight

Author:
Oliver Schirokauer

Journal:
Math. Comp. **79** (2010), 583-602

MSC (2000):
Primary 11Y16; Secondary 11T71, 11Y05, 11Y40

DOI:
https://doi.org/10.1090/S0025-5718-09-02198-X

Published electronically:
July 27, 2009

MathSciNet review:
2552242

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We define the weight of an integer to be the smallest such that can be represented as , with . Since arithmetic modulo a prime of low weight is particularly efficient, it is tempting to use such primes in cryptographic protocols. In this paper we consider the difficulty of the discrete logarithm problem modulo a prime of low weight, as well as the difficulty of factoring an integer of low weight. We describe a version of the number field sieve which handles both problems. In the case that , the method is the same as the special number field sieve, which runs conjecturally in time for . For fixed , we conjecture that there is a constant less than such that the running time of the algorithm is at most for . We further conjecture that no less than has this property. Our analysis reveals that on average the method performs significantly better than it does in the worst case. We consider all the examples given in a recent paper of Koblitz and Menezes and demonstrate that in every case but one, our algorithm runs faster than the standard versions of the number field sieve.

**[1]**J. P. Buhler, H. W. Lenstra Jr., and Carl Pomerance,*Factoring integers with the number field sieve*, The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, Berlin, 1993, pp. 50–94. MR**1321221**, https://doi.org/10.1007/BFb0091539**[2]**E. R. Canfield, Paul Erdős, and Carl Pomerance,*On a problem of Oppenheim concerning “factorisatio numerorum”*, J. Number Theory**17**(1983), no. 1, 1–28. MR**712964**, https://doi.org/10.1016/0022-314X(83)90002-1**[3]**An Commeine and Igor Semaev,*An algorithm to solve the discrete logarithm problem with the number field sieve*, Public key cryptography—PKC 2006, Lecture Notes in Comput. Sci., vol. 3958, Springer, Berlin, 2006, pp. 174–190. MR**2423189**, https://doi.org/10.1007/11745853_12**[4]**Michael Filaseta,*A further generalization of an irreducibility theorem of A. Cohn*, Canad. J. Math.**34**(1982), no. 6, 1390–1395. MR**678678**, https://doi.org/10.4153/CJM-1982-097-3**[5]**Antoine Joux and Reynald Lercier,*Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method*, Math. Comp.**72**(2003), no. 242, 953–967. MR**1954978**, https://doi.org/10.1090/S0025-5718-02-01482-5**[6]**Neal Koblitz and Alfred Menezes,*Pairing-based cryptography at high security levels*, Cryptography and coding, Lecture Notes in Comput. Sci., vol. 3796, Springer, Berlin, 2005, pp. 13–36. MR**2235246**, https://doi.org/10.1007/11586821_2**[7]**Arjen K. Lenstra,*Unbelievable security (Matching AES security using public key systems)*, Advances in cryptology—ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comput. Sci., vol. 2248, Springer, Berlin, 2001, pp. 67–86. MR**1934516**, https://doi.org/10.1007/3-540-45682-1_5**[8]**A. K. Lenstra and H. W. Lenstra Jr. (eds.),*The development of the number field sieve*, Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, Berlin, 1993. MR**1321216****[9]**A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse, and J. M. Pollard,*The number field sieve*, The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, Berlin, 1993, pp. 11–42. MR**1321219**, https://doi.org/10.1007/BFb0091537**[10]**Gurmeet Singh Manku and Joe Sawada,*A loopless Gray code for minimal signed-binary representations*, Algorithms—ESA 2005, Lecture Notes in Comput. Sci., vol. 3669, Springer, Berlin, 2005, pp. 438–447. MR**2257959**, https://doi.org/10.1007/11561071_40**[11]**Kevin S. McCurley,*The discrete logarithm problem*, Cryptology and computational number theory (Boulder, CO, 1989) Proc. Sympos. Appl. Math., vol. 42, Amer. Math. Soc., Providence, RI, 1990, pp. 49–74. MR**1095551**, https://doi.org/10.1090/psapm/042/1095551**[12]**Oliver Schirokauer,*Discrete logarithms and local units*, Philos. Trans. Roy. Soc. London Ser. A**345**(1993), no. 1676, 409–423. MR**1253502**, https://doi.org/10.1098/rsta.1993.0139**[13]**O. Schirokauer,*The impact of the number field sieve on the discrete logarithm problem*, Algorithmic Number Theory: Lattices, Number Fields, Curves, and Cryptography, Mathematical Sciences Research Institute Publications, Cambridge University Press, Cambridge, 2008.**[14]**J. Solinas,*Generalized Mersenne numbers*, Technical Report CORR 99-39 (1999).**[15]**P. Stevenhagen,*The number field sieve*, Algorithmic Number Theory: Lattices, Number Fields, Curves, and Cryptography, Mathematical Sciences Research Institute Publications, Cambridge University Press, Cambridge, 2008.**[16]**P. Stevenhagen and H. W. Lenstra Jr.,*Chebotarëv and his density theorem*, Math. Intelligencer**18**(1996), no. 2, 26–37. MR**1395088**, https://doi.org/10.1007/BF03027290

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
11Y16,
11T71,
11Y05,
11Y40

Retrieve articles in all journals with MSC (2000): 11Y16, 11T71, 11Y05, 11Y40

Additional Information

**Oliver Schirokauer**

Affiliation:
Department of Mathematics, Oberlin College, Oberlin, Ohio 44074

Email:
oliver.schirokauer@oberlin.edu

DOI:
https://doi.org/10.1090/S0025-5718-09-02198-X

Keywords:
Discrete logarithm,
integer factorization,
number field sieve

Received by editor(s):
July 31, 2006

Received by editor(s) in revised form:
June 15, 2008

Published electronically:
July 27, 2009

Article copyright:
© Copyright 2009
American Mathematical Society