Polynomial selection for the number field sieve
Date
2011
Authors
Bai, Shi
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The number field sieve is asymptotically the most efficient algorithm known for factoring large integers. It consists of several stages, the first one being polynomial selection. The running time of subsequent steps depends on the quality of the chosen polynomials. In the thesis, we discuss the current state of the art in polynomial selection. Polynomial selection can be divided into three stages: polynomial generation, size optimization and root optimization. We give some analysis of polynomial generation algorithms. We then describe some improvements for polynomial size optimization and root optimization. The size optimization is based on determining a translation and then locally optimizing the polynomial. The root optimization is based on Hensel's lifting lemma and a root sieve on congruences classes modulo small prime powers. The improvements described here have been implemented and used to obtain some good polynomials in practice. We also discuss some recent progress on polynomial selection using lattice reduction.
Description
Keywords
Citation
Collections
Source
Type
Thesis (PhD)
Book Title
Entity type
Access Statement
Open Access
License Rights
Restricted until
Downloads
File
Description