Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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 $ N$ to be the smallest $ w$ such that $ N$ can be represented as $ \sum _{i=1}^{w} \epsilon _{i} 2^{c_{i}}$, with $ \epsilon _{1},\ldots ,\epsilon _{w}\in \{1,-1\}$. 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 $ N$ of low weight, as well as the difficulty of factoring an integer $ N$ of low weight. We describe a version of the number field sieve which handles both problems. In the case that $ w=2$, the method is the same as the special number field sieve, which runs conjecturally in time $ \exp (((32/9)^{1/3}+o(1))(\log N)^{1/3}(\log \log N)^{2/3})$ for $ N\to \infty $. For fixed $ w>2$, we conjecture that there is a constant $ \xi $ less than $ (32/9)^{1/3}((2w-3)/(w-1))^{1/3}$ such that the running time of the algorithm is at most $ \exp ((\xi +o(1))(\log N)^{1/3}(\log \log N)^{2/3})$ for $ N\to \infty $. We further conjecture that no $ \xi $ less than $ (32/9)^{1/3}((\sqrt {2}w-2\sqrt {2}+1)/(w-~1))^{2/3}$ 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.


References [Enhancements On Off] (What's this?)

  • [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)

Similar Articles

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

American Mathematical Society