The Number Field Sieve For Integers Of Low Weight

Title:
The Number Field Sieve For Integers Of Low Weight
Authors:
Schirokauer, Oliver
Abstract:
We define the weight of an integer N to be the smallest w such that N can be represented as E-i=1(w) epsilon(i)2(ci), with epsilon(i), ... , epsilon(w) is an element of {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 -> infinity. 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 -> infinity. We further conjecture that no xi less than (32/9)(1/3)((root 2w - 2 root 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.
Citation:
Schirokauer, Oliver. 2010. "The Number Field Sieve For Integers Of Low Weight." Mathematics Of Computation 79(269): 583-602.
Publisher:
American Mathematical Society
DATE ISSUED:
2010-01
Department:
Mathematics
Type:
article
PUBLISHED VERSION:
10.1090/S0025-5718-09-02198-X
PERMANENT LINK:
http://hdl.handle.net/11282/309913

Full metadata record

DC FieldValue Language
dc.contributor.authorSchirokauer, Oliveren_US
dc.date.accessioned2013-12-23T16:20:56Zen
dc.date.available2013-12-23T16:20:56Zen
dc.date.issued2010-01en
dc.identifier.citationSchirokauer, Oliver. 2010. "The Number Field Sieve For Integers Of Low Weight." Mathematics Of Computation 79(269): 583-602.en_US
dc.identifier.issn0025-5718en_US
dc.identifier.urihttp://hdl.handle.net/11282/309913en
dc.description.abstractWe define the weight of an integer N to be the smallest w such that N can be represented as E-i=1(w) epsilon(i)2(ci), with epsilon(i), ... , epsilon(w) is an element of {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 -> infinity. 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 -> infinity. We further conjecture that no xi less than (32/9)(1/3)((root 2w - 2 root 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.en_US
dc.language.isoen_USen_US
dc.publisherAmerican Mathematical Societyen_US
dc.identifier.doi10.1090/S0025-5718-09-02198-Xen
dc.subject.departmentMathematicsen_US
dc.titleThe Number Field Sieve For Integers Of Low Weighten_US
dc.typearticleen_US
dc.identifier.journalMathematics Of Computationen_US
dc.subject.keywordDiscrete logarithmen_US
dc.subject.keywordInteger factorizationen_US
dc.subject.keywordNumber field sieveen_US
dc.subject.keywordMathematics, applieden_US
dc.identifier.volume79en_US
dc.identifier.issue269en_US
dc.identifier.startpage583en_US
All Items in The Five Colleges of Ohio Digital Repository are protected by copyright, with all rights reserved, unless otherwise indicated.