# [Resource Topic] 2006/107: The number field sieve for integers of low weight

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.

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.