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
Liste complète des métadonnées

Cited literature [13 references]  Display  Hide  Download
Contributor : Alexander Kruppa <>
Submitted on : Thursday, November 6, 2008 - 4:49:23 PM
Last modification on : Thursday, January 11, 2018 - 6:21:04 AM
Document(s) archivé(s) le : Saturday, November 26, 2016 - 3:05:49 AM


Publisher files allowed on an open archive




Peter Lawrence Montgomery, Alexander Kruppa. Improved Stage 2 to P$\pm$1 Factoring Algorithms. 8th International Symposium on Algorithmic Number Theory - ANTS-VIII, May 2008, Waterloo, Canada. pp.180-195, ⟨10.1007/978-3-540-79456-1_12⟩. ⟨inria-00188192v3⟩



Record views


Files downloads