Fully deterministic ECM

Iram Chelli 1, *
* Auteur correspondant
1 CACAO - Curves, Algebra, Computer Arithmetic, and so On
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Résumé : Nous présentons un algorithme FDECM permettant d'extraire - si ils existent - tous les facteurs premiers inférieurs ou égaux à $ 2^{32} $ d'un nombre composé donné en entrée $n$. La méthode naïve par ``trial-division'' ou par produit suivi de pgcd sont toutes deux extrêmement lentes et inadaptées dans la pratique. Nous montrons dans cet article qu'avec FDECM cela coûte moins de 100 courbes elliptiques bien choisies, ce qui peut être très rapide avec une implantation d'ECM et des bornes $B_1$, $B_2$ bien optimisées. Le temps d'exécution dépend de la taille du nombre $n$ en entrée. Nous avons pris soin de rendre notre algorithme le plus indépendant possible d'une implémentation particulière par le choix de la paramétrisation des courbes utilisées et la vérification systématique avec Magma. Finalement, nous envisageons differentes possibilités d'optimisation à FDECM en utilisant une famille rationnelle de paramètres pour ECM et en déterminant à quel moment le passage au GCD devient moins coûteux qu'ECM et ce pour différentes tailles du nombre $n$ en entrée. C'est, à notre connaissance, la première description détaillée d'un algorithme d'ECM complètement déterministe.
Type de document :
Rapport
[Research Report] RR-7040, INRIA. 2009, pp.26
Liste complète des métadonnées

https://hal.inria.fr/inria-00419083
Contributeur : Iram Chelli <>
Soumis le : mardi 22 septembre 2009 - 15:50:09
Dernière modification le : jeudi 11 janvier 2018 - 06:21:04
Document(s) archivé(s) le : mardi 16 octobre 2012 - 11:10:38

Fichier

RR-7040.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00419083, version 1

Collections

Citation

Iram Chelli. Fully deterministic ECM. [Research Report] RR-7040, INRIA. 2009, pp.26. 〈inria-00419083〉

Partager

Métriques

Consultations de la notice

135

Téléchargements de fichiers

168