IdentifiantMot de passe
Mot de passe oublié ?Je m'inscris ! (gratuit)

Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous
Identifiant
Mot de passe
Mot de passe oublié ?
Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

Tutoriel sur l'algorithme ECM de factorisation par les courbes elliptiques
Par Laurent Ott

Le , par laurent_ott
4 commentaires

0PARTAGES

14  0 
Bonjour.
J'ai le plaisir de vous présenter ce tutoriel :

Algorithme ECM de factorisation par les courbes elliptiques

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.

Une erreur dans cette actualité ? Signalez-le nous !

4 commentaires
Commenter Signaler un problème
ijk-ref
Avatar de ijk-ref
Membre éclairé https://www.developpez.com
Le 25/06/2021 à 13:55
= 3² ou -3²
= 3² ou (-3)²

Merci pour ton tutoriel
3  0 
laurent_ott
Avatar de laurent_ott
Rédacteur https://www.developpez.com
Le 25/06/2021 à 14:54
Citation Envoyé par ijk-ref Voir le message
= 3² ou (-3)²
Bonjour.
Je viens de rectifier.
Idem pour (-1)².

Merci pour cette remarque.
Cordialement.
1  0 
BrunoVDR
Avatar de BrunoVDR
Candidat au Club https://www.developpez.com
Le 08/08/2021 à 17:57
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.
1  0 
laurent_ott
Avatar de laurent_ott
Rédacteur https://www.developpez.com
Le 08/08/2021 à 18:33
Bonjour.
Effectivement les articles de vulgarisation sur ce sujet sont rares. Je pensais avoir mal cherché mais vous confirmez.
Quant au seuil de fiabilité, je n'ai pas trouvé de réponse. C'est pourquoi j'ai utilisé cette formule qui ne contient pas une coquille, car le logarithme peut être écrit ln ou Log suivant les langages de programmation.
Donc à adapter à votre situation, voire trouver une meilleure formule.
En espérant que cette documentation soit assez claire pour convertir l'algorithme à votre langage de programmation.
Bonne continuation.
0  0