Factorisation des entiers avec la méthode ECM de Lenstra
Bonjour.
Je vous sollicite pour m’aider à comprendre la méthode factorisation des entiers avec la méthode ECM de Lenstra, car mes faibles notions en mathématiques ne me permettent pas de tout comprendre.
J’arrive à factoriser de petits nombres, par exemple « 55215650826521 », mais avec des temps de traitements 100 fois plus longs qu’avec la méthode RhoPollard, ce qui n’est pas normal, il doit donc me manquer une pièce dans ce puzzle !
Voici comment je procède avec N le nombre à factoriser :
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| 1. Je prends des entiers au hasard pour un point P1(x, y) et un entier a.
2. Je recherche le point suivant, P2(x,y) :
s = (3x² + a) / 2y
s = s modulo N
Si s < 0 alors s = N s
x = s² - 2x
y = s(x x) y
3. Je boucle tant quune solution nest pas trouvée pour former d'autres points :
P(i) = P1 + P(i-1) avec
si x <> x(i-1) alors
s = ( y(i-1) y ) / ( x(i-1) x ) Modulo N
Note : si le numérateur ou le dénominateur de s ont un PGCD commun avec N alors une solution est trouvée.
sinon
s = ( 3x² + a ) / ( 2y ) Modulo N
Note : si le numérateur ou le dénominateur de s ont un PGCD commun avec N alors une solution est trouvée.
dans les deux cas
si s < 0 alors s = N s
x(i) = s² - x(i-1) x modulo N
si x(i) < 0 alors x(i) = N s
y(i) = s ( x - x(i) ) y
4. Au bout de trop dessais je repars en 1 |
Je pense que quelque chose m’échappe.
Peut-être du côté du calcul du modulo. En effet j’ai trouvé une documentation où je ne m’explique pas le résultat du modulo :
Avec N=3397, x=3, y=-8, a=4
s = (3x²+a) / (2y) = (3 x 3² - 4) / (2 x -8) = 31 / -16 = 635 modulo 3397
Comment ce 635 peut-il être trouvé ?
C'est pour moi un grand mystère.
Et pourtant la suite du traitement reprend ce 635 indispensable :
x(i) = s² - x(i-1) – x modulo N
x(i) = 635² - 3 - 3 = 403219 MOD 3397 = 2373
y(i) = s ( x - x(i) ) – y = 635 ( 3 - 2373) - (-8) = -1504942 MOD 3397 = -71 soit -71 + 3397 = 3326
puis dans le calcul du point suivant :
s = 3334 / 2370 et comme PGCD(2370,3397) = 79 soit la solution.
Dans l'attente de vos réponses.
Cordialement.