# The Number Field Sieve For Integers Of Low Weight

- Title:
- The Number Field Sieve For Integers Of Low Weight
- Authors:
- 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:
- 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 Field | Value | Language |
---|---|---|

dc.contributor.author | Schirokauer, Oliver | en_US |

dc.date.accessioned | 2013-12-23T16:20:56Z | en |

dc.date.available | 2013-12-23T16:20:56Z | en |

dc.date.issued | 2010-01 | en |

dc.identifier.citation | Schirokauer, Oliver. 2010. "The Number Field Sieve For Integers Of Low Weight." Mathematics Of Computation 79(269): 583-602. | en_US |

dc.identifier.issn | 0025-5718 | en_US |

dc.identifier.uri | http://hdl.handle.net/11282/309913 | en |

dc.description.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. | en_US |

dc.language.iso | en_US | en_US |

dc.publisher | American Mathematical Society | en_US |

dc.identifier.doi | 10.1090/S0025-5718-09-02198-X | en |

dc.subject.department | Mathematics | en_US |

dc.title | The Number Field Sieve For Integers Of Low Weight | en_US |

dc.type | article | en_US |

dc.identifier.journal | Mathematics Of Computation | en_US |

dc.subject.keyword | Discrete logarithm | en_US |

dc.subject.keyword | Integer factorization | en_US |

dc.subject.keyword | Number field sieve | en_US |

dc.subject.keyword | Mathematics, applied | en_US |

dc.identifier.volume | 79 | en_US |

dc.identifier.issue | 269 | en_US |

dc.identifier.startpage | 583 | en_US |

All Items in The Five Colleges of Ohio Digital Repository are protected by copyright, with all rights reserved, unless otherwise indicated.