Paper 2006/107
The number field sieve for integers of low weight
Oliver Schirokauer
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. Our analysis leads to the conjecture that, for $N\to\infty$ with $w$ fixed, the worstcase running time of the method is bounded above by ${\rm exp}((c+o(1))(\log\,N)^{1/3}(\log\log\,N)^{2/3})$ with $c<((32/9)(2w3)/(w1))^{1/3}$ and below by the same expression with $c=(32/9)^{1/3}((\sqrt{2}w2\sqrt{2}+1)/(w1))^{2/3}.$ It also 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.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 discrete logarithminteger factorizationnumber field sieve
 Contact author(s)
 oliver schirokauer @ oberlin edu
 History
 20060319: received
 Short URL
 https://ia.cr/2006/107
 License

CC BY
BibTeX
@misc{cryptoeprint:2006/107, author = {Oliver Schirokauer}, title = {The number field sieve for integers of low weight}, howpublished = {Cryptology ePrint Archive, Paper 2006/107}, year = {2006}, note = {\url{https://eprint.iacr.org/2006/107}}, url = {https://eprint.iacr.org/2006/107} }