Fully deterministic ECMReportar como inadecuado




Fully deterministic ECM - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

* Corresponding author 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.





Autor: Iram Chelli -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados