You are looking at a specific version 20060319:211157 of this paper. See the latest version.

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 worst-case 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)(2w-3)/(w-1))^{1/3}$ and below by the same expression with $c=(32/9)^{1/3}((\sqrt{2}w-2\sqrt{2}+1)/(w-1))^{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)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
discrete logarithminteger factorizationnumber field sieve
Contact author(s)
oliver schirokauer @ oberlin edu
History
2006-03-19: received
Short URL
https://ia.cr/2006/107
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.