Improved Stage 2 to P$\pm$1 Factoring Algorithms

Peter-Lawrence Montgomery 1 Alexander Kruppa 2
2 CACAO - Curves, Algebra, Computer Arithmetic, and so On
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Some implementations of stage 2 of the P-1 method of factorization use convolutions. We describe a space-efficient implementation, allowing convolution lengths around 2^23 and stage 2 limit around 10^16 while attempting to factor 230-digit numbers on modern PC's. We use the discrete cosine transform to multiply reciprocal polynomials. We present adjustments for the P+1 algorithm. We list some new findings.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal.inria.fr/inria-00188192
Contributor : Alexander Kruppa <>
Submitted on : Tuesday, January 15, 2008 - 10:51:26 AM
Last modification on : Thursday, January 11, 2018 - 6:21:04 AM
Long-term archiving on : Monday, October 22, 2012 - 12:11:46 PM

Files

pm1fft.submitted2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00188192, version 2

Citation

Peter-Lawrence Montgomery, Alexander Kruppa. Improved Stage 2 to P$\pm$1 Factoring Algorithms. 2008. ⟨inria-00188192v2⟩

Share

Metrics

Record views

5

Files downloads

35