The number field sieve for integers of low weight (original) (raw)

Paper 2006/107

The number field sieve for integers of low weight

Oliver Schirokauer

Abstract

We define the weight of an integer NNN to be the smallest www such that NNN can be represented as sumi=1wepsiloni2ci\sum_{i=1}^w \epsilon_i 2^{c_i}sumi=1wepsiloni2ci, with epsilon1,ldots,epsilonwin1,−1\epsilon_1,\ldots,\epsilon_w\in\{1,-1\}epsilon1,ldots,epsilonwin1,−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 NNN of low weight, as well as the difficulty of factoring an integer NNN of low weight. We describe a version of the number field sieve which handles both problems. Our analysis leads to the conjecture that, for NtoinftyN\to\inftyNtoinfty with www fixed, the worst-case running time of the method is bounded above by rmexp((c+o(1))(log,N)1/3(loglog,N)2/3){\rm exp}((c+o(1))(\log\,N)^{1/3}(\log\log\,N)^{2/3})rmexp((c+o(1))(log,N)1/3(loglog,N)2/3) with c<((32/9)(2w−3)/(w−1))1/3c<((32/9)(2w-3)/(w-1))^{1/3}c<((32/9)(2w−3)/(w−1))1/3 and below by the same expression with c=(32/9)1/3((sqrt2w−2sqrt2+1)/(w−1))2/3.c=(32/9)^{1/3}((\sqrt{2}w-2\sqrt{2}+1)/(w-1))^{2/3}.c=(32/9)1/3((sqrt2w−2sqrt2+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{cryptoeprint:2006/107, author = {Oliver Schirokauer}, title = {The number field sieve for integers of low weight}, howpublished = {Cryptology {ePrint} Archive, Paper 2006/107}, year = {2006}, url = {https://eprint.iacr.org/2006/107} }