Factoring Small to Medium Size Integers: An Experimental Comparison

Jérôme Milan 1
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : We report on our experiments in factoring integers from 50 to 200 bit with the NFS postsieving stage or class group structure computations as potential applications. We implemented, with careful parameter selections, several general-purpose factoring algorithms suited for these smaller numbers, from Shanks's square form factorization method to the self-initializing quadratic sieve, and revisited the continued fraction algorithm in light of recent advances in smoothness detection batch methods. We provide detailed timings for our implementations to better assess their relative range of practical use on current commodity hardware.
Type de document :
Pré-publication, Document de travail
Fixed a stupid but glaring mistake in the description of the ECM algorithm. 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00188645
Contributeur : Jérôme Milan <>
Soumis le : vendredi 29 janvier 2010 - 14:30:00
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : mercredi 30 novembre 2016 - 11:47:32

Fichier

smallint_expcomp_draft_02_1.pd...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00188645, version 3

Collections

Citation

Jérôme Milan. Factoring Small to Medium Size Integers: An Experimental Comparison. Fixed a stupid but glaring mistake in the description of the ECM algorithm. 2010. 〈inria-00188645v3〉

Partager

Métriques

Consultations de la notice

578

Téléchargements de fichiers

525