Montgomery's method of polynomial selection for the number field sieve

Nicholas Coxon 1
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : The number field sieve is the most efficient known algorithm for factoring large integers that are free of small prime factors. For the polynomial selection stage of the algorithm, Montgomery proposed a method of generating polynomials which relies on the construction of small modular geometric progressions. Montgomery's method is analysed in this paper and the existence of suitable geometric progressions is considered.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal.inria.fr/hal-01097069
Contributor : Nicholas Coxon <>
Submitted on : Thursday, December 18, 2014 - 5:11:01 PM
Last modification on : Tuesday, December 18, 2018 - 4:18:25 PM
Long-term archiving on : Monday, March 23, 2015 - 5:27:00 PM

Files

montgomery.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Nicholas Coxon. Montgomery's method of polynomial selection for the number field sieve. 2014. ⟨hal-01097069⟩

Share

Metrics

Record views

500

Files downloads

280