Discussion :

[laurent_ott]

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 C :

Sélectionner tout - Visualiser dans une fenêtre à part

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 qu’une solution n’est 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 d’essais 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.

[Flodelarab]

Bonjour

Je pense que quelque chose m’échappe.

Le somme des points, non ?

P est un point de courbe elliptique.
Q est un point de la courbe elliptique.
P+Q est point de la courbe elliptique.
P+P est un point de la courbe elliptique.
P+P+P+...+P+P+P = nP = 0 aboutit à un groupe cyclique comme Z\nZ.

L'erreur classique des internautes avec "des faibles notions en mathématiques" est de faire les calculs sur les nombres entiers, alors qu'on parle de points de courbe elliptique.

Dans ton cas, j'imagine que 3398P = P.

[laurent_ott]

Dans ton cas, j'imagine que 3398P = P.

Bonjour. Et merci d'avoir pris le temps d'apporter une réponse même si, malheureusement, je n'ai rien compris.
Je ne sais pas qui t'a mis un pouce négatif, mais ce n'est pas moi.
Si quelqu'un peut apporter une aide plus adaptée à mes faibles notions, je suis preneur.
Cordialement.

[laurent_ott]

Bonjour.
J’ai trouvé pourquoi (31/-16) MOD 3397 = 635

Pour deux raisons :

La première, c’est qu’il faut retraiter la fraction pour retrouver l’inverse modulo, c’est-à-dire retrouver la valeur de x dans :
16x MOD 3397 = 1

Ça peut se faire par la force brute :
16 x 1 MOD 3397 = 16
16 x 2 MOD 3397 = 32
16 x … MOD 3397 = …
16 x 637 MOD 3397 = 1

Ou par cet algorithme :

Code VBA :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
'------------------------------------------------------------------------------------------------
Function InversMod(ByVal A, ByVal B) 
'------------------------------------------------------------------------------------------------
Dim Q, T, X, Y
X = 1: Y = 0
While (B <> 0)
    T = B
    Q = Int(A / T)
    B = A - Q * T
    A = T
    T = X
    X = Y - Q * T
    Y = T
Wend
InversMod = CDec(Y)
If Y < 0 Then InversMod = CDec(Y + NbB)
End Function
'------------------------------------------------------------------------------------------------

Donc (31 x 637) MOD 3397 = 2762

Mais ici, deuxième raison, un des termes est négatif, -16 et non pas 16, donc il faut ôter cette valeur à 3397 :
3397 – 2762 = 635

Bon, je continue mes recherches sur la méthode ECM car j’ai encore des zones sombres à éclaircir.
Si vous le souhaitez, votre aide sera la bienvenue.
Cordialement.