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.
Type de document :
Communication dans un congrès
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

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00188192
Contributeur : Alexander Kruppa <>
Soumis le : jeudi 6 novembre 2008 - 16:49:23
Dernière modification le : jeudi 11 janvier 2018 - 06:21:04
Document(s) archivé(s) le : samedi 26 novembre 2016 - 03:05:49

Fichier

pm1fft-final.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

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〉

Partager

Métriques

Consultations de la notice

246

Téléchargements de fichiers

323