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 :
Conference papers
Alfred J. van der Poorten and Andreas Stein. 8th International Symposium on Algorithmic Number Theory - ANTS-VIII, May 2008, Waterloo, Canada. Springer, 5011, pp.180-195, 2008, Lecture Notes in Computer Science. 〈10.1007/978-3-540-79456-1_12〉
Liste complète des métadonnées

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/inria-00188192
Contributor : Alexander Kruppa <>
Submitted on : Thursday, November 6, 2008 - 4:49:23 PM
Last modification on : Tuesday, October 25, 2016 - 5:02:40 PM
Document(s) archivé(s) le : Saturday, November 26, 2016 - 3:05:49 AM

File

pm1fft-final.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Peter Lawrence Montgomery, Alexander Kruppa. Improved Stage 2 to P$\pm$1 Factoring Algorithms. Alfred J. van der Poorten and Andreas Stein. 8th International Symposium on Algorithmic Number Theory - ANTS-VIII, May 2008, Waterloo, Canada. Springer, 5011, pp.180-195, 2008, Lecture Notes in Computer Science. 〈10.1007/978-3-540-79456-1_12〉. 〈inria-00188192v3〉

Share

Metrics

Record views

195

Files downloads

206