Better polynomials for GNFS

Shi Bai 1 Cyril Bouvier 2 Alexander Kruppa 2 Paul Zimmermann 2
1 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
2 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : The general number field sieve (GNFS) is the most efficient algo-rithm known for factoring large integers. It consists of several stages, the first one being polynomial selection. The quality of the selected polynomials can be modelled in terms of size and root properties. We propose a new kind of polynomials for GNFS: with a new degree of freedom, we further improve the size property. We demonstrate the efficiency of our algorithm by exhibiting a better polynomial than the one used for the factorization of RSA-768, and a polynomial for RSA-1024 that outperforms the best published one.
Type de document :
Article dans une revue
Mathematics of Computation / Mathematics of Computation, American Mathematical Society, 2016, 85, pp.12. <10.1090/mcom3048>
Liste complète des métadonnées


https://hal.inria.fr/hal-01089507
Contributeur : Cyril Bouvier <>
Soumis le : lundi 1 décembre 2014 - 20:47:56
Dernière modification le : mardi 22 novembre 2016 - 15:18:00
Document(s) archivé(s) le : lundi 2 mars 2015 - 13:38:18

Fichier

sopt-20140905.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Shi Bai, Cyril Bouvier, Alexander Kruppa, Paul Zimmermann. Better polynomials for GNFS. Mathematics of Computation / Mathematics of Computation, American Mathematical Society, 2016, 85, pp.12. <10.1090/mcom3048>. <hal-01089507>

Partager

Métriques

Consultations de
la notice

912

Téléchargements du document

416