Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

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
Email: oliver.schirokauer@oberlin.edu

DOI: http://dx.doi.org/10.1090/S0025-5718-09-02198-X
PII: S 0025-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