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., C. Pomerance,*Factoring integers with the number field sieve*, in [8], pp. 50-94. MR**1321221****[2]**E.R. Canfield, P. Erdös, C. Pomerance,*On a problem of Oppenheim concerning "factorisatio numerorum"*, J. Number Theory**17**(1983), 1-28. MR**712964 (85j:11012)****[3]**A. Commeine, I. Semaev,*An algorithm to solve the discrete logarithm problem with the number field sieve*, Public Key Cryptography, Lecture Notes in Comput. Sci., vol. 3958, Springer-Verlag, Berlin, 2006, pp. 174-190. MR**2423189****[4]**M. Filaseta,*A further generalization of an irreducibility theorem of A. Cohn*, Canad. J. Math.**34**(1982), 1390-1395. MR**678678 (85g:11014)****[5]**A. Joux, R. Lercier,*Improvements on the general number field sieve for discrete logarithms in prime fields*, Math. Comp.**72**(2003), 953-967. MR**1954978 (2003k:11192)****[6]**N. Koblitz, A. Menezes,*Pairing-based cryptography at high security levels*, Cryptography and Coding: 10th IMA International Conference, Lecture Notes in Comput. Sci, vol. 3796, Springer-Verlag, Berlin, 2005, pp. 13-36. MR**2235246 (2007b:94235)****[7]**A.K. Lenstra,*Unbelievable security: Matching AES security using public key systems*, Advances in Cryptology - ASIACRYPT 2001, Lecture Notes in Comput. Sci., vol. 2248, Springer-Verlag, Berlin, 2001, pp. 67-86. MR**1934516 (2003h:94042)****[8]**A.K. Lenstra, H.W. Lenstra, Jr., (eds.),*The development of the number field sieve*, Lecture Notes in Mathematics, 1554, Springer-Verlag, Berlin, 1993. MR**1321216 (96m:11116)****[9]**A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse, J.M. Pollard,*The number field sieve*, in [8], pp. 11-42. MR**1321219****[10]**G. Manku, J. Sawada,*A loopless Gray code for minimal signed-binary representations*, 13th Annual European Symposium on Algorithms, Lecture Notes in Comput. Sci., vol. 3669, Springer-Verlag, Berlin, 2005, pp. 438-447. MR**2257959****[11]**K. McCurley,*The discrete logarithm problem*, Cryptology and Computational Number Theory, Proc. Sympos. Appl. Math., vol. 42, Amer. Math. Soc., Providence, RI, 1990, pp. 49-74. MR**1095551 (92d:11133)****[12]**O. Schirokauer,*Discrete logarithms and local units*, Theory and Applications of Numbers without Large Prime Factors, Philos. Trans. Roy. Soc. London, Ser. A, vol. 345, Royal Society, London, 1993, pp. 409-424. MR**1253502 (95c:11156)****[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, H.W. Lenstra, Jr.,*Chebotarëv and his density theorem*, The Mathematical Intelligencer**18**(1996), 26-37. MR**1395088 (97e:11144)**

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