The number field sieve for integers of low weight
Author:
Oliver Schirokauer
Journal:
Math. Comp. 79 (2010), 583602
MSC (2000):
Primary 11Y16; Secondary 11T71, 11Y05, 11Y40
Published electronically:
July 27, 2009
MathSciNet review:
2552242
Fulltext PDF
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, http://dx.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
(85j:11012), http://dx.doi.org/10.1016/0022314X(83)900021
 [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
(2009g:11163), http://dx.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
(85g:11014), http://dx.doi.org/10.4153/CJM19820973
 [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 (electronic). MR 1954978
(2003k:11192), http://dx.doi.org/10.1090/S0025571802014825
 [6]
Neal
Koblitz and Alfred
Menezes, Pairingbased cryptography at high security levels,
Cryptography and coding, Lecture Notes in Comput. Sci., vol. 3796,
Springer, Berlin, 2005, pp. 13–36. MR 2235246
(2007b:94235), http://dx.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
(2003h:94042), http://dx.doi.org/10.1007/3540456821_5
 [8]
A.
K. Lenstra and H.
W. Lenstra Jr. (eds.), The development of the number field
sieve, Lecture Notes in Mathematics, vol. 1554, SpringerVerlag,
Berlin, 1993. MR
1321216 (96m:11116)
 [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, http://dx.doi.org/10.1007/BFb0091537
 [10]
Gurmeet
Singh Manku and Joe
Sawada, A loopless Gray code for minimal signedbinary
representations, Algorithms—ESA 2005, Lecture Notes in Comput.
Sci., vol. 3669, Springer, Berlin, 2005, pp. 438–447. MR
2257959, http://dx.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
(92d:11133), http://dx.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
(95c:11156), http://dx.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 9939 (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
(97e:11144), http://dx.doi.org/10.1007/BF03027290
 [1]
 J.P. Buhler, H.W. Lenstra, Jr., C. Pomerance, Factoring integers with the number field sieve, in [8], pp. 5094. MR 1321221
 [2]
 E.R. Canfield, P. Erdös, C. Pomerance, On a problem of Oppenheim concerning "factorisatio numerorum", J. Number Theory 17 (1983), 128. 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, SpringerVerlag, Berlin, 2006, pp. 174190. MR 2423189
 [4]
 M. Filaseta, A further generalization of an irreducibility theorem of A. Cohn, Canad. J. Math. 34 (1982), 13901395. 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), 953967. MR 1954978 (2003k:11192)
 [6]
 N. Koblitz, A. Menezes, Pairingbased cryptography at high security levels, Cryptography and Coding: 10th IMA International Conference, Lecture Notes in Comput. Sci, vol. 3796, SpringerVerlag, Berlin, 2005, pp. 1336. 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, SpringerVerlag, Berlin, 2001, pp. 6786. 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, SpringerVerlag, 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. 1142. MR 1321219
 [10]
 G. Manku, J. Sawada, A loopless Gray code for minimal signedbinary representations, 13th Annual European Symposium on Algorithms, Lecture Notes in Comput. Sci., vol. 3669, SpringerVerlag, Berlin, 2005, pp. 438447. 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. 4974. 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. 409424. 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 9939 (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), 2637. 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:
http://dx.doi.org/10.1090/S002557180902198X
PII:
S 00255718(09)02198X
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
