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
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?)

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

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