International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

The number field sieve for integers of low weight

Authors:
Oliver Schirokauer
Download:
URL: http://eprint.iacr.org/2006/107
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2006-21600,
  title={The number field sieve for integers of low weight},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / discrete logarithm, integer factorization, number field sieve},
  url={http://eprint.iacr.org/2006/107},
  note={ oliver.schirokauer@oberlin.edu 13226 received 17 Mar 2006, last revised 18 Mar 2006},
  author={Oliver Schirokauer},
  year=2006
}