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{ϵ}_i{2}^{c_i}$, with ${ϵ}_1,\dots ,{ϵ}_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 \mathrm{\infty }$ with $w$ fixed, the worst-case running time of the method is bounded above by $$ with $$ and below by the same expression with $$ 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.