Welcome to the resource topic for
**2006/107**

**Title:**

The number field sieve for integers of low weight

**Authors:**
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.

**ePrint:**
https://eprint.iacr.org/2006/107

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .