Fully deterministic ECM
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.
Origine : Fichiers produits par l'(les) auteur(s)
Commentaire : Erratum: in the end of Section 2.2.1, replace the formula B = (2a^3/9-a)/3b^2 by B = (2a^3/9-a)/3b^3 (the denominator 3b^2 is replaced by 3b^3).
Commentaire : Erratum: in the end of Section 2.2.1, replace the formula B = (2a^3/9-a)/3b^2 by B = (2a^3/9-a)/3b^3 (the denominator 3b^2 is replaced by 3b^3).