The number field sieve for integers of low weight

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.