Improved Stage 2 to P$\pm$1 Factoring Algorithms - Archive ouverte HAL Access content directly
Conference Papers Year : 2008

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

(1) , (2)
1
2

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.
Fichier principal
Vignette du fichier
pm1fft-final.pdf (251.7 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

inria-00188192 , version 1 (15-11-2007)
inria-00188192 , version 2 (15-01-2008)
inria-00188192 , version 3 (06-11-2008)

Identifiers

Cite

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⟩
96 View
752 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More