Apprendre à programmer l'algorithme ECM de factorisation par les courbes elliptiques
Bonjour.
J'ai le plaisir de vous présenter ce tutoriel :
Dans cet article, vous allez apprendre à programmer l’algorithme ECM de Hendrik Lenstra qui utilise les courbes elliptiques pour factoriser un nombre entier.
Cette méthode est bien adaptée à la recherche de « petits facteurs », car sa complexité ne dépend pas de la taille du nombre à factoriser, mais de la taille du plus petit de ses facteurs.
Vous pouvez apporter vos avis dans cette discussion.
Bonne lecture.
Sur le calcul arbitraire de B, le seuil de friabilité.
Bonjour, et tout d'abord merci pour cet article de qualité.
Les articles sur le sujet sont rares, mais ceux qui citent leur sources et detaillent les choses a ce point le sont encore plus :) .
J'ai développé une librairie d'arithmetique modulaire sur de grands entiers de taille fixe que j'utilise entre autre pour des calculs sur courbes elliptiques. Apres avoir implementé Pollard Rho, j'aimerais maintenant essayer cet algorithme de factorization. Ma difficulté est sans surprise d'adapter le seuil de friabilité B, aux entiers que je manipule (256bits). J'ai étudié l'equation arbitraire que vous donnez mais Il me semble qu'une erreur s'y soit glissée :
"B = Entier(2,718281828459 Puissance(0,5 x Racine(Log(1234567890) x Log(Log(1234567890))))) = 54"
Le calcul qui donne le resultat arrondi de 54 serait selon moi:
B = Entier(2,718281828459 Puissance(0,5 x Racine(ln(1234567890) x ln(ln(1234567890))))) = 54 a moins que dans le langage utilisé la fonction Log utilise e comme base par défaut.
Merci encore pour cet Article.