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 : Thursday, November 15, 2007 - 6:42:13 PM
Last modification on : Thursday, January 11, 2018 - 6:21:04 AM
Long-term archiving on : Monday, April 12, 2010 - 2:23:25 AM

Files

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

Identifiers

  • HAL Id : inria-00188192, version 1

Citation

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

Share

Metrics

Record views

3

Files downloads

41