TIPE - Courbes elliptiques et factorisation

(version détaillée)

Samuel MIMRAM
2001–2002

Dernière révision : 17 mai 2006.

Table des matières

1 Les courbes elliptiques, définitions, propriétés 2
1.1 Définition des courbes elliptiques . . . . . . . . . . . . . . . . . . 2
1.2 Structure de groupe abélien . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Approche géométrique de la loi de la sécante-tangente . . 5
1.2.2 Expression analytique de ∗ . . . . . . . . . . . . . . . . . 6
1.3 Cardinalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Un test de primalité 8

3 Une méthode de factorisation 9

4 Résultats inutilisés 11
4.1 Précisions à propos de la définition . . . . . . . . . . . . . . . . . 11
4.2 Autres propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2.1 L’algorithme de Shanks . . . . . . . . . . . . . . . . . . . 14
4.2.2 L’algorithme de Schoof . . . . . . . . . . . . . . . . . . . . 14
4.3 Le critère de Pocklington . . . . . . . . . . . . . . . . . . . . . . 16
4.4 Le critère de Goldwasser-Kilian dans Z/nZ . . . . . . . . . . . . 17

5 Notre implémentation 18
5.1 Détails de la mise en œuvre . . . . . . . . . . . . . . . . . . . . . 18
5.1.1 La classe ec point . . . . . . . . . . . . . . . . . . . . . . 18
5.1.2 Calcul de kP . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.1.3 Calcul des inverses . . . . . . . . . . . . . . . . . . . . . . 20
5.1.4 Le ppcm(1, 2, . . . , B) . . . . . . . . . . . . . . . . . . . . . 21
5.1.5 La procédure principale . . . . . . . . . . . . . . . . . . . 21
5.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.2.1 109849677793909 = 239633 · 11131 · 41183 . . . . . . . . . 23
5.2.2 2974015455045701710807 = 206083 · 64849 · 34729 · 6407749 23
5.2.3 19480333860937071253 = 1562513 · 6512647 · 1914323 . . . 24
5.2.4 134755010254579987971511 = 61494437·42398497·51684299 24
5.2.5 Limites de l’implémentation . . . . . . . . . . . . . . . . . 24

1
Une décomposition : la factorisation
Dans ce tipe, nous allons définir des ensembles particuliers appelés courbes
elliptiques et munir ces derniers d’une structure de groupe. Nous proposerons
ensuite une méthode basée sur l’utilisation de ces groupes pour décomposer un
“grand” entier en produit de facteurs premiers. Cette méthode est, à l’heure
actuelle, la plus rapide pour factoriser les entiers compris entre 106 et 1030 . Elle
a été trouvée en 1985 par Lenstra.

1 Les courbes elliptiques, définitions, propriétés

1.1 Définition des courbes elliptiques
Définition 1 (Plan projectif). On appelle plan projectif sur
un corps K l’en-
semble, noté P2 (K), des classes d’équivalence K3 \{(0, 0, 0)} /R, où R est une
relation d’équivalence définie par :

3 2
∀ ((a, b, c) , (a′ , b′ , c′ )) ∈ K3 \{(0, 0, 0)} ,
(a, b, c)R(a′ , b′ , c′ ) ⇔ [∃t ∈ K\{0}, (a, b, c) = t(a′ , b′ , c′ )]
Pratiquement, cela revient à “projeter l’espace sur une demi-sphère” centrée en
(0, 0, 0).

représentants principaux classe d’équivalence

b

Définition 2 (Courbe elliptique). On appelle courbe elliptique sur un corps

K, notée E(K), une courbe cubique dans le plan projectif P2 (K) i.e. définie par
F (X, Y, Z) = 0 où F est un polynôme de degré 3, homogène en trois variables,
à coefficients dans K :
F (X, Y, Z) = α1 X 3 +α2 Y 3 +α3 Z 3 +α4 X 2 Y +α5 X 2 Z+α6 Y 2 X+α7 Y 2 Z+α8 Z 2 X+α9 Z 2 Y +α10 XY Z = 0
et munie d’une origine O ∈ E(K).
Remarque 3. Dans la suite, nous nous intéresserons aux courbes elliptiques non
singulières i.e. :
 
∂F ∂F ∂F
∀P ∈ E(K), (P ), (P ), (P ) 6= (0, 0, 0)
∂X ∂Y ∂Z

2
définies sur un corps K de caractéristique différente de 2 ou 3.
Lorsqu’il n’y a pas d’ambiguité sur le corps, nous noterons indifféremment les
courbes E(K) ou E.
Proposition 4. Soit E une courbe elliptique. On peut se ramener à une équation
de E, dite forme courte de Weierstrß :
E : Y 2 Z = X 3 + aXZ 2 + bZ 3 (1)
X
On peut alors écrire cette équation en coordonnées non homogènes (x = Z et
y = YZ ) :
E : y 2 = x3 + ax + b (2)
plus le point O = (0, 1, 0) qui est le seul point à l’infini (Z = 0) et que l’on
choisit comme origine.
Démonstration. Par un changement de variables homographique, on peut tou-
jours se ramener à une équation dite forme générale de Weierstraß :
Y 2 Z + a1 XY Z + a3 Y Z 2 = X 3 + a2 X 2 Z + a4 XZ 2 + a6 Z 3 (3)
a2 +4a
les changements de variable Y ← (Y − 21 (a1 X + a3 )) et X ← (X − 1 12 2 Z)
permettent alors d’aboutir au résultat souhaité. On peut remarquer que l’on doit
avoir 2 6= 0 et 12 6= 0 d’où la nécessité que K soit de caractéristique différente
de 2 ou 3.
Théorème 5. Soit E une courbe donnée par une équation de Weierstraß. Alors
E est non singulière si et seulement si la quantité ∆ = 4a3 + 27b2 est non nulle.
Démonstration. Montrons d’abord que le point à l’infini O = (0, 1, 0) n’est
jamais singulier. Regardons E comme une courbe de P2 (K) donnée par son
équation :
F (X, Y, Z) = Y 2 Z − X 3 − aXZ 2 − bZ 3 = 0
On a : ∂F 2 2 ∂F


∂Z = Y − 2aXZ − 3bZ donc : ∂Z (O) = 1 6= 0 ; O n’est jamais un
point singulier de E.
Pour les autres points considérons la définition de la courbe E par son équation
de Weierstraß réduite :
E : f (x, y) = y 2 − x3 − ax − b = 0
La courbe est singulière en un point P0 = (x0 , y0 ) ∈ E si et seulement si :
 
∂f 2
 ∂x (x0 , y0 ) = 3x0 + a = 0


 
 ∂f

 (x0 , y0 ) = 2y0 = 0
∂y
soit encore :
 x2 = − a

0
3
y =0
0

Car 2 6= 0 et 3 6= 0. Or P0 est un point de la courbe, par conséquent y02 = 0 =

9b2
x30 + ax0 + b = 32 ax0 + b. Il s’ensuit que x20 = 4a a 3 2
2 = − 3 soit ∆ = 4a + 27b = 0.

Finalement si E est non singulière si et seulement si ∆ 6= 0

3
1.2 Structure de groupe abélien
Montrons que l’on peut munir une courbe elliptique d’une structure de
groupe abélien.
Proposition 6. Soit E une courbe elliptique et D une droite définies sur un
corps K. Si E a au moins deux points d’intersection (comptés avec leur multipli-
cité) avec la droite D, alors E a exactement trois points d’intersection (comptés
avec leur multiplicité) avec la droite D.
Démonstration. On suppose que E est définie par E : f (x, y) = y 2 − (x3 + ax +
b) = 0 ∪ O = (0, 1, 0). On suppose que D n’est pas verticale (x 6= constante) et
qu’elle est décrite par l’équation y = αx + β. Les points d’intersection de E et D
vérifient f (x, αx + β) = 0, soit P (x) = x3 − αx2 + (a − 2αβ)x + (b − β) = 0. Soit
P1 = (x1 , y1 ) et P2 = (x2 , y2 ) deux points d’intersection de E et D (différents
de O). x1 et x2 sont donc deux racines réelles de P qui est un polynôme de
degré 3 et admet donc une et une seule autre racine réelle x3 (pas forcément
distincte de x1 et x2 ). Le point P3 = (x3 , αx3 + β) sera alors le troisième point
d’intersection de E et D.
On peut étendre cette démonstration au cas où D est verticale en montrant
qu’alors le troisième point d’intersection est O. De plus, dans le cas où par
exemple P2 = O, on aura P3 = (x1 , −y1 ).

4
 1.2.1 Approche géométrique de la loi de la sécante-tangente
Soit E une courbe elliptique définie sur P2 (K) par :

E : Y 2 Z = X 3 + aXZ 2 + b (4)
X Y
soit encore en coordonnées non homogènes (en posant x = Z et y = Z) :

E : y 2 = x3 + ax + b ∪ O = (0, 1, 0) (5)

On peut alors définir sur E une loi de composition ∗ dite loi de composition de
la sécante-tangente :
– si (P, Q) ∈ E 2 avec P 6= Q, on définit P ∗ Q comme étant le troisième
point d’intersection de la droite D passant par P et Q avec E

O
10 10
9 9
8 8
7
P*Q 7 P
6 6
5 5
4 4
3 3
Q
2 2
1 1
0 0
-4 -3 -2 -1 -1 0 1 2 3 4 5 6 -4 -3 -2 -1 -1 0 1 2 3 4 5 6
-2 -2
-3 -3
P -4 -4
-5 -5
-6 -6
-7 -7
-8
P+Q -8 Q
-9 -9
-10 -10

Fig. 1 – Calcul de P ∗ Q dans la courbe elliptique E : y 2 = x3 − 4x + 2 ∪ O

– si P ∈ E, on définit P ∗ P comme étant le troisième point d’intersection

de la droite D tangente à la courbe en P avec E (P est alors considéré
comme un point double d’intersection)

10
9
8
7
6
5
4

P 3 P*P
2
1
0
-4 -3 -2 -1 -1 0 1 2 3 4 5 6
-2
-3
-4
-5
P+P
-6
-7
-8
-9
-10

Fig. 2 – Calcul de P ∗ P dans la courbe elliptique E : y 2 = x3 − 4x + 2 ∪ O

Remarque 7. On a aussi représenté P + Q = O ∗ (P ∗ Q).

5
1.2.2 Expression analytique de ∗
Soit E une courbe elliptique définie par :

E : f (x, y) = y 2 − (x3 + ax + b) = 0 ∪ O = (0, 1, 0) avec 4a3 + 27b2 6= 0 (6)

Proposition 8. Soit P1 = (x1 , y1 ), P2 = (x2 , y2 ) et P3 = (x3 , y3 ) trois points

de E\{O} tels que P1 6= P2 . Si x1 6= x2 et si P3 = P1 ∗ P2 , alors
(
x3 = λ2 − x1 − x2
y3 = λ(x3 − x1 ) + y1

y2 −y1
avec λ = x2 −x1 .

Démonstration. Si x2 6= x1 alors la sécante D passant par P1 et P2 a pour pente

λ = xy22 −x
−y1
1
. Soit γ = y1 − λx1 . L’équation de D est alors : y = λx + γ. On a
alors :

f (x, λx + γ) = (λx + γ)2 − (x3 + ax + b)

= −x3 + λ2 x2 + (2λγ − a)x + (γ 2 − b)

Or les points P1 , P2 et P3 sont racines de f car ils appartiennent à la courbe E.

De plus ils appatiennent à la droite D. On doit donc avoir : f (x1 , λx1 + γ) =
f (x2 , λx2 + γ) = f (x3 , λx3 + γ) = 0. x1 , x2 et x3 étant distincts, ce sont donc
les trois racines du polynôme de degré 3 : −x3 + λ2 x2 + (2λγ − a)x + (γ 2 − b).
D’où :

−x3 +λ2 x2 + (2λγ − a)x + (γ 2 − b)

= −(x − x1 )(x − x2 )(x − x3 )
= −x3 + (x1 + x2 + x3 )x2 − (x1 x2 + x1 x3 + x2 x3 )x + (x1 x2 x3 )

Par identification du coefficient de x2 , on obtient : x3 = λ2 − x1 − x2 . De plus :

y3 = (y3 − y1 ) + y1 = λ(x3 − x1 ) + y1 .
Remarque 9. Cette définition est encore vraie dans le cas où x1 = x2 et y2 = −y1
avec P1 ∗ P2 = O.
Proposition 10. Soit P1 = (x1 , y1 ) et P2 = (x2 , y2 ) deux points de E\{O}. Si
P2 = P1 ∗ P1 , alors

x3 = λ2 − x1 − x2
y3 = λ(x3 − x1 ) + y1

3x21 +a
avec λ = 2y1 .
∂f
1 (P ) 3x21 +a
Démonstration. La tangente D à E en P1 a pour pente : λ = − ∂x
∂f
(P )
= 2y1 .
∂y 1

Soit γ = y1 − λx1 . L’équation de D est alors : y = λx + γ. Et la démonstration

est alors identique à celle de la proposition 8.

6
Remarque 11. Le fait d’avoir imposé que la courbe soit non singulière nous
permet d’être assurés que la tangente existera toujours.
Proposition 12. On a de plus O ∗ O = O.
Démonstration. Si E est définie par F (X, Y, Z) = Y 2 Z−(X 3 +aXZ 2 +bZ 3 ) = 0,
∂F ∂F
on a : ∂X = −3X 2 − aZ 2 , ∂Y = 2Y Z et ∂F 2 2
∂Z = Y − 2aXZ − 3bZ . Donc un
−−→
vecteur normal à la courbe a pour coordonnées : gradF (O) = (0, 0, 1). Le plan
d’équation Z = 0 est donc un plan tangent à la courbe en O (c’est une droite du
plan projectif P2 (K)). Or F (X, Y, 0) = 0 ⇔ X 3 = 0. Le point O = (0, 1, 0) est
donc le seul point (triple) d’intersection de la tangente à la courbe en O avec la
courbe. Donc O ∗ O = O.
Proposition 13. Si P2 = O ∗ P1 ou P2 = P1 ∗ O alors

x2 = x1
y2 = −y1

Remarque 14. La loi de composition interne ∗ est commutative par construction

mais n’est pas, a priori, associative.
Corollaire 15. Soit E est une courbe elliptique définie sur un corps K, soit P1
et P2 deux points de E. Alors l’opération + définie par

∀(P1 , P2 ) ∈ E, P1 + P2 = O ∗ (P1 ∗ P2 )

permet de munir E d’une structure de groupe abélien (commutatif ) admettant

O comme élément neutre.
De plus, supposons P1 = (x1 , y1 ) 6= O et P2 = (x2 , y2 ) 6= O. Si x1 = x2 et
y2 = −y1 alors P1 + P2 = O ; dans les autres cas, si P3 = (x3 , y3 ) = P1 + P2 ,
alors

x3 = λ2 − x1 − x2
y3 = λ(x1 − x3 ) − y1

où (y
2 −y1
x2 −x1 si P 6= Q
λ= 3x21 +a
2y1 si P = Q
On a enfin
∀P ∈ E, P + O = O + P = P
Démonstration. + ainsi définie est une loi de composition interne. Le fait que
O est élément neutre découle de la remaque 12. L’existence d’un inverse est
immédiate avec la proposition 13. On vérifie de plus que + est associative.
Remarque 16. Cette proposition est encore vraie dans les cas où K est un corps
de caractéristique 2 ou 3.
Remarque 17. Le calcul de λ fait appel à un inverse (dans K) ce qui justifie la
nécessité pour K d’être un corps.

7
1.3 Cardinalité
Remarque 18. Si p est un nombre premier, on notera dans la suite Fp un corps
fini de cardinal p.
Théorème 19 (Théorème de Hasse). Soit p un nombre premier. Si E(Fp )
est une courbe elliptique définie sur le corps fini Fp de cardinalité p alors la
cardinalité #E(Fp ) de E(Fp ) vérifie
√
|p + 1 − #E(Fp )| ≤ 2 p (7)

Remarque 20. Deuring a montré que pour tout entier premier p, pour tout entier
√ √
e compris entre p + 1 − 2 p et p + 1 + 2 p, il existe une courbe elliptique E(Fp )
telle que #E = e. C’est donc le meilleur encadrement possible.

2 Un test de primalité
Proposition 21 (Critère de Goldwasser-Kilian). Soit N ∈ N premier avec 6
(i.e. divisible ni par 2, ni par 3). S’il existe un entier m et un point P de la
courbe elliptique

E : y 2 ≡ x3 + ax + b (mod N ) ∪ O = (0, 1, 0)

tels que
1. il existe un facteur premier q de m strictement supérieur à (N 1/4 + 1)2
2. mP = O = (0, 1, 0)
m
3. q P = (x, y, z) avec z ∈ (Z/N Z)∗
alors N est premier.
Démonstration. Raisonnons par l’absurde. Supposons que N a un facteur pre-
mier p. Notons E ′ la courbe E modulo p, m′ la cardinalité de E ′ et P ′ le point
de E ′ correspondant au point P de E. Par hypothèse, mP = O et m q P 6= O sur
E et donc mP ′ = O (car p|N ) et m q P ′
=
6 O (car z ∈ (Z/N Z)∗
). Ceci implique
′ ′
que q divise l’ordre de P comme point de E , d’où, d’après le théorème de
Lagrange, q divise m′ . Il s’ensuit, d’après le théorème de Hasse (théorème 19)
que :
√ √
q ≤ m′ ≤ p + 1 + 2 p = ( p + 1)2
√
≤ (N 1/4 + 1)2 car p étant un facteur premier de N , p ≤ N

Il y a contradiction avec l’hypothèse.

Remarque 22. Nous faisons tous les calculs comme si N était premier. Si l’algo-
rithme de Schoof (qui est l’algorithme le plus efficace pour calculer la cardinalité
de E) n’aboutit pas, alors cela signifie que N est composé. De même, lors du
calcul de mP et de m q P , il est possible que le dénominateur intervenant dans le
calcul de λ ne soit pas inversible. Cela signifie que Z/N Z n’est pas un corps et
donc que N est composé (par le théorème de Bezout). Nous avons alors prouvé
que N n’est pas premier.

8
3 Une méthode de factorisation
L’algorithme de factorisation utilisant les courbes elliptiques est une variante
de la méthode p − 1 de Pollard dans Fp .
Qm
Définition 23 (B-lissité). Soit N ∈ N et soit N = i=1 pα i la décomposition
i

de N en facteurs premiers.
N est dit B-lisse si et seulement si :

∀i ∈ |[1, m]|, pi ≤ B

N est dit B-superlisse si et seulement si :

∀i ∈ |[1, m]|, pα
i ≤B
i

Méthode 24 (p − 1 de Pollard). Soit N ∈ N un entier à factoriser. On suppose

que N admet un facteur premier p tel que p − 1 soit B-superlisse. On a alors :
(p − 1)|ppcm(1, 2, . . . , B) d’où, d’après le petit théorème de Fermat :

∀a ∈ N, a ∧ N = 1 ⇒ appcm(1,2,...,B) ≡ 1 (mod p)

Par conséquent :
l = [(appcm(1,2,...,B) − 1) ∧ N ] > 1
Si l 6= N , on a alors trouvé un facteur non trivial de N , sinon nous calculons l
pour une autre valeur de a ; si l = 1, nous augmentons la valeur de B.
L’avantage de la méthode de Lenstra, basée sur les courbes elliptiques, est
qu’elle ne nécessite pas, contrairement à la méthode p − 1 de Pollard, que N ait
un facteur premier p tel que p − 1 soit B-superlisse.

Méthode 25 (de Lenstra). Soit N ∈ N un entier, supposé non premier, admet-

tant un facteur premier p (que l’on veut trouver). Voici les étapes du déroulement
de la méthode de Lenstra pour la factorisation de N à l’aide de la courbe ellip-
tique E définie par :

E : y 2 = x3 + ax + b ∪ O = (0, 1, 0)

où a et b sont des entiers. On supposera la cardinalité de #E(Fp ) B-superlisse.

– On vérifie que N n’est divisible ni par 2, ni par 3 (sinon, on a trouvé
un facteur de N ) pour nous assurer que Z/pZ sera de caractéristique
différente de 2 ou 3.
– En notant ∆ = 4a3 + 27, on vérifie que ∆ ∧ N = 1 pour nous assurer que
E(Z/N Z) est non singulière. Si 1 < ∆ ∧ N < N alors nous avons trouvé
un facteur non trivial de N et si ∆ ∧ N = N alors nous choisissons une
autre courbe elliptique (d’autres valeurs de a, b et B).

9
 – On choisit un point P ∈ E(Z/N Z)\{O}. #E(Fp ) étant supposée B-
superlisse, #E(Fp ) divise k = ppcm(1, 2, . . . , B). D’où, d’après le théorème
de Lagrange, l’ordre de P divise k donc kP = O. Si l’on calculait kP =
P + P + . . . + P dans E(Fp ), on serait alors amené à calculer Q + P = O
avec Q = k ′ P et k ′ < k. En pratique, on va effectuer le calcul de kP non
pas dans E(Fp ) mais dans E(Z/N Z).
Rappelons les formules d’addition pour R = P + Q avec P 6= O et Q 6= O
où P = (x1 , y1 ), Q = (x2 , y2 ) et R = (x3 , y3 ) :
– si x1 = x2 et y2 = −y1 alors P + Q = O
– sinon
x3 = λ2 − x1 − x2
y3 = λ(x1 − x3 ) − y1

où (y
2 −y1
x2 −x1 si P 6= Q
λ= 3x21 +a
2y1 si P = Q
On aura P + Q = O donc x1 ≡ x2 (mod p), soit p|x1 − x2 . Mais il se peut
que l’on ait : x1 6≡ x2 (mod N ). Lors du calcul λ pour additionner Q et P ,
(x1 − x2 ) ne sera alors pas inversible (dans Z/N Z) car p|pgcd(x1 − x2 , N )
donc (x1 − x2 ) ∧ N 6= 1. Dans ce cas, si 1 < (x1 − x2 ) ∧ N < N alors nous
avons trouvé un facteur non trivial de N et si (x1 − x2 ) ∧ N = N alors
nous choisissons un autre courbe elliptique.
Si le calcul de kP dans E(Z/N Z) aboutit alors nous choisissons une autre
courbe elliptique.

Pour le choix de la borne de lissité, on peut tenir

√ le raisonnement suivant :
si p est un facteur premier de N alors p < N ; or, d’après le théorème
√
de Hasse (théorème 19), on a #E(Fp ) < ( p + 1)2 . On peut donc prendre
B ≥ ⌈(N 1/4 + 1)2 ⌉.

Remarque 26. Dans la pratique, pour des raisons évidentes de rapidité de calcul,
on ne prend pas k = ppcm(1, 2, . . . , B) mais simplement k = ppcm(B, B − 1).
Cela diminue la probabilité de trouver un facteur premier mais améliore de
beaucoup la rapidité de l’algorithme.

Remarque 27. De plus, plus au lieu de l’addition naı̈ve, le calcul de kP est ef-
fectué avec l’exponentiation rapide ; le principe reste cependant valable.

Remarque 28. Pour le choix de P dans Ea,b , on peut imposer b = −a, ce qui
permet d’être assuré que P = (1, 1) appartient à la courbe elliptique.

Il a été montré que le temps moyen d’aboutissement de cette méthode est

en O(e(1+ε) ln N ln ln N ).

L’inconvénient de cette méthode est qu’elle n’est pas, stricto sensu, un algo-
rithme car elle n’aboutit pas forcément à un résultat. Il faut lui adjoindre des
tests de primalité (il en existe utilisant les courbes elliptiques).

10
4 Résultats inutilisés
4.1 Précisions à propos de la définition
Définition 29 (Courbe elliptique). Soit K un corps. On appelle courbe ellip-
tique sur K une courbe E dans le plan projectif P2 (K), cubique 1 , sans points
singuliers 2 et munie d’un point distingué O ∈ E.
Par un changement de variables homographique, on peut toujours se ramener
à une équation dite de Weierstraß (forme générale) :
Y 2 Z + a1 XY Z + a3 Y Z 2 = X 3 + a2 X 2 Z + a4 XZ 2 + a6 Z 3 (8)
Pour alléger les notations, on peut écrire l’équation de Weierstraß en coor-
données non homogènes (x = X Y
Z et y = Z ) :

E : y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 (9)
plus le point (0, 1, 0) qui est le seul point à l’infini (Z = 0) et que l’on choisit
comme point distingué O.

On définit alors les quantités suivantes :

b2 = a21 + 4a2 , b4 = 2a4 + a1 a3 , b6 = a33 + 4a6 ,
b8 = a21 a6 + 4a2 a6 − a1 a3 a4 + a2a23 − a24 ,
c4 = b22 − 24b4 et c6 = −b32 + 36b2 b4 − 216b6
Définition 30 (Discriminant). On appelle discriminant ∆ de l’équation de
Weierstraß la quantité
∆ = −b22 b8 − 8b34 − 27b26 + 9b2 b4 b6 (10)
Définition 31 (j-invariant). On appelle j-invariant de la courbe elliptique E
la quantité
c3
j(E) = 4 (11)
∆
Théorème 32. Si K est de caractéristique p autre que 2 ou 3, on peut toujours
trouver une “forme courte” de Weierstraß, i.e. mettre E sous la forme :
y 2 = x3 + ax + b (12)
dans ce cas on a :
4a3
∆ = −16(4a3 + 27b2 ) et j(E) = 1728 (13)
4a3 + 27b2
Démonstration. Si p 6= 2, alors 2 6= 0K . On peut donc faire le changement de
variable y ← (y − 21 (a1 x + a3 )) et on obtient : y 2 = x3 + b42 x2 + b24 x + b46 .
b2
Si de plus p 6= 3, on peut faire le changement de variable x ← (x − 12 ) pour
2 3 c4 c6 c4
obtenir : y = x − 48 x − 864 . D’où le résultat cherché en posant a = − 48 et
c6
b = − 864 .
1 i.e. définie par F (X, Y, Z) = 0 où F est un polynôme de degré 3, homogène en trois

variables, à coefficients
“ dans K ”
2 i.e. : ∀P ∈ E, ∂F (P ), ∂F (P ), ∂F (P ) 6= (0, 0, 0)
∂X ∂Y ∂Z

11
Remarque 33. Dans les cas où p = 2 ou 3 on a , suivant p et j(E) :

p j(E) E: ∆ j(E)
2 0 y 2 + cy = x3 + ax + b c4 0
2 6= 0 y 2 + xy = x3 + ax2 + b a 1/a
3 0 y 2 = x3 + ax + b −a3 0
3 6= 0 y 2 = x3 + ax2 + b −a3 b −a3 /b

Lemme 34. Soit E une courbe donnée par son équation de Weierstraß générale :

E : f (x, y) = y 2 + a1 xy + a3 y − x3 − a2 x2 − a4 x − a6 = 0

dont le discriminant vaut ∆ et le j-invariant j(E). Le changement de variables

(x, y) ← (u2 x + r, u3 y + u2 sx + t) avec r, s, t, u ∈ K 4 et u 6= 0

transforme l’équation précédente en

E ′ : f ′ (x, y) = y 2 + a′1 xy + a′3 y − x3 − a′2 x2 − a′4 x − a′6 = 0

où les coefficients sont donnés par

ua′1 = a1 + 2s
u2 a′2 = a2 − sa1 + 3r − s2
u3 a′3 = a3 + ra1 + 2t
u4 a′4 = a4 − sa3 + 2ra2 − (t + rs)a1 + 3r2 − 2st

De plus u12 ∆′ = ∆ et j(E ′ ) = j(E).

Théorème 35. Soit E une courbe donnée par une équation de Weierstraß.
Alors E est non singulière si et seulement si ∆ 6= 0.
Démonstration. (⇐) Soit l’équation générale de Weierstraß :

E : f (x, y) = y 2 + a1 xy + a3 y − x3 − a2 x2 − a4 x − a6 = 0

On suppose que son discriminant ∆ est non nul.

Montrons d’abord que le point à l’infini O = (0, 1, 0) n’est jamais singulier.
Regardons E comme une courbe de P2 donnée par son équation :

F (W, Y, Z) = Y 2 Z + a1 XY Z + a3 Y Z 2 − X 3 − a2 X 2 Z − a4 XZ 2 − a6 Z 3 = 0

Comme ∂F


∂Z (O) = 1 6= 0, O n’est jamais un point singulier de E.
Raisonnons par l’absurde et supposons que E soit singulière en un point P0 =
(x0 , y0 ). Par le changement de variables (x, y) ← (x − x0 , y − y0 ), nous ramenons
le point P0 en (0, 0). D’après le lemme 34, cette transformation ne modifie
 pas le
∂f
discriminant (car u = 1). Nous avons alors a6 = f (0, 0) = 0,a4 = ∂x (0, 0) = 0
 
et a3 = ∂f ∂y (0, 0) = 0. La courbe E a donc pour équation :

E : f (x, y) = y 2 + a1 xy − x3 − a2 x2 = 0

12
Or le discriminant de cette équation est nul : il y a contradiction avec l’hy-
pothèse. La courbe E n’a donc aucun point singulier.

(⇒) On ne s’intéressera ici qu’au cas où la caractéristique p de K est

différente de 2 et de 3. La courbe E est alors donnée par l’équation de Weierstraß
réduite :
E : f (x, y) = y 2 − (x3 + ax + b) = 0
Raisonnons par l’absurde. Si la courbe est singulière en un point P0 = (x0 , y0 ) ∈
E, alors :
 
∂f a4
(x0 , y0 ) = 3x20 + a4 = 0 ⇒ x20 = −
∂x 3
 
∂f
(x0 , y0 ) = 2y0 = 0 ⇒ y0 = 0
∂y

Or P0 est un point de la courbe, par conséquent y02 = 0 = x30 +ax0 +b = 23 ax0 +b.
9b2 a
Il s’ensuit que x20 = 4a 3 2
2 = − 3 et donc ∆ = −16(4a + 27b ) = 0. Finalement si

E est non singulière alors ∆ 6= 0

4.2 Autres propriétés

Définition 36 (Isogénie). Soit E et E ′ deux courbes elliptiques définies sur un
corps K. Une isogénie (homomorphisme de courbes elliptiques) de E dans E ′
est une application rationnelle φ (homomorphisme de courbes algébrique) non
identiquement nulle et telle que φ(O) = O′ .
Théorème 37. Si φ est une isogénie de E dans E ′ , alors c’est un homomor-
phisme du groupe (E, +E ) dans (E ′ , +E ′ ).
Remarque 38. Soit E une courbe elliptique. Soit m un entier. La multiplication
par m (au sens de la loi de groupe) est une isogénie notée :

[m]E : E → E
P 7→ mP

Définition 39 (Degré). Le noyau d’une isogénie φ : E → E ′ est donc un

sous-groupe fini de E. On appelle degré de φ l’ordre de Ker φ.
Remarque 40. Si E est une courbe elliptique définie sur un corps K, on notera
E(m) le noyau de [m]E défini sur K, la clôture algébrique de K.
Définition 41 (Isogénie duale). Soit φ : E → E ′ une isogénie de degré d. Alors
il existe une unique isogénie φ̂ : E ′ → E telle que φ̂ ◦ φ = [d]E ′ . On l’appelle
isogénie duale de φ.
Théorème 42. Deux courbes elliptiques sont isogènes sur le corps Fq si et
seulement si elles ont même cardinalité.

13
Théorème 43. Tout isomorphisme (isogénie bijective) de courbes elliptiques
est de la forme :
(x, y) ← (u2 x + r, u3 y + u2 sx + t) avec r, s, t, u ∈ K 4 et u 6= 0
Théorème 44. Deux courbes données par leur équation de Weierstraß dont le
discriminant est non nul sont isomorphes si et seulement si elles ont le même
j-invariant.
Théorème 45. Soit E une courbe elliptique sur le corps fini Fq . Alors le groupe
(E, +) est ou bien cyclique, ou bien isomorphe à Z/n1 Z × Z/n2 Z avec n2 |(n1 ∧
p − 1).

4.2.1 L’algorithme de Shanks

Algorithme 46 (“Pas de bébé, pas de géant”). D’après le théorème de Hasse
(théorème 19), l’ordre d’une courbe elliptique E définie sur Fq est de la forme
√ √
#E = p + 1 − c où c est un entier de l’intervalle [−2 q, 2 q]. Pour un point P
choisi aléatoirement dans E on doit alors avoir : (q + 1 − c)P = 0.
√
L’énumération naı̈ve nécessiterait O( q) opérations dans Fq .
L’idée de Shanks est basée sur le fait que la calcul d’un opposé d’un point de E
est immédiat (corollaire 15). Pour P ∈ E il suffit donc de chercher deux entiers
1/4 1/4
c0 et c1 respectivement dans [0, 2q 1/4 ] et dans [− q 2 , q 2 ] tels que

(q + 1 − c1 4⌈q 1/4 ⌉)P = ±c0 P

on pose alors c = ±c0 + c1 4⌈q 1/4 ⌉ et q + 1 − c est un multiple de l’ordre de P
(et l’ordre de P divise l’ordre de E).
L’algorithme comporte deux phases :
– la phase des “pas de géant” qui consiste à stocker dans une table les
⌈q 1/4 ⌉ + 1 points (q + 1 − c1 4q 1/4 )P
– la phase des “pas de bébé” qui consiste à calculer les points c0 P pour c0
variant de 0 à 2⌈q 1/4 ⌉ et à vérifier si les points c0 P et −c0 P correspondent
à une entrée dans la première table
On peut en moyenne espérer, avec cet algorithme, une complexité totale de
O(q 1/4 ln2 q).

4.2.2 L’algorithme de Schoof

Définition 47 (Frobenius). Soit E une courbe elliptique définie sur un corps
fini Fq de caractéristique p. L’automorphisme de Frobenius est défini par
φE : E(Fq ) → E(Fq )
(
O si P = O
P 7→ q q
(x , y ) si P = (x, y)

Théorème 48. Le polynôme caractéristique de φE est

φ2E − [c]E ◦ φE + [q]E = 0 (14)
où c est défini par
#E(Fq ) = q + 1 − c

14
 √
Remarque 49. D’après le théorème de Hasse (théorème 19), on a : |c| ≤ 2 q.
Définition 50 (Polynômes de division). Avec les notations de la définition 29,
les polynômes de division fm (X) d’une courbe elliptique E sont définis par

f0 (X) = 0
f1 (X) = 1
f2 (X) = 1
f3 (X) = 3X 4 + b2 X 3 + 3b4 X 2 + 3b6 X + b6
f4 (X) = 2X 6 + b2 X 5 + 5b4 X 4 + 10b6 X 3 + 10b8 X 2 + (b2 b8 − b4 b6 )X + (b4 b8 − b26 )

et, en posant F (X) = 4X 3 + b2 X 2 + 2b4 X + b6 ,

2 2
f2m = fm (fm+2 fm−1 − fm−3 fm+1 )
(
F 2 fm+2 fm
3 3
− fm−1 fm+1 si m est pair
f2m+1 =
fm+2 fm − fm−1 fm+1 F 2 sinon
3 3

m2 +1 m2 −1
Le polynôme fm est de degré au plus 2 si m est impair et 2 si m est
pair.
Théorème 51. Soit E une courbe elliptique définie sur un corps K, P un point
de K et m ∈ N∗ . Alors
(
O si P ∈ E[m]
[m]E (P ) =  φm (x,y) ωm (x,y) 
ψ 2 (x,y) , ψ 3 (x,y)
m m
si P = (x, y) ∈ E(K)\E[m]

où les polynômes vérifient ψm , φm et ωm satisfont (avec les notations de la

définition 29)
(
(2Y + a1 X + a3 )fm si m est pair
ψm =
fm sinon

et
2
φm = Xψm − ψm−1 ψm+1
2 2
2ψm ωm = ψ2m − ψm (a1 ψm + a3 ψm )

Remarque 52. Ce théorème nous fournit une construction explicite de [m]E .

Théorème 53. Soit P ∈ E(K). Alors P ∈ E[m] si et seulement si P = O

(trivial) ou, lorsque P (x, y), si fm (x) = 0.
Algorithme 54 (Algorithme de Schoof). Soit E une courbe elliptique définie
sur Fq . L’idée de Schoof est de restreindre l’équation caractéristique du Frobe-
nius (14) aux sous-groupes E[l] (où l ∈ N∗ ) et E(Fq ) ce qui donne

∀l ∈ N∗ , φ2E[l] + [q mod l]E[l] = [c mod l]E[l] ◦ φE[l] (15)

15
soit encore
2 2
∀l ∈ N∗ , ∀(x, y) ∈ E[l], (xq , y q ) + [q mod l](x, y) = [c mod l](xq , y q )

où c est tel que #E(Fq ) = q + 1 − c.

L’algorithme consiste à calculer le membre de gauche de l’équation (15) pour un
point P d’ordre l, dans E(Fq ) ; puis à calculer [θ]E[l] (φE[l] (P )) pour θ dans Fl
jusqu’à ce que l’égalité (15) soit vérifiée. Lorsque c’est le cas, nous avons c ≡ θ
(mod l). Il ne reste Q plus qu’á répéter ce calcul pour des entiers l premiers entre
√
eux etvérifiant l > 4 q pour trouver c à l’aide du théorème chinois qui stipule
que si l1 , . . . , ln sont n entiers de N\{0, 1}Qpremiers entre eux deux à deux alors
n
Z/l1 Z × . . . × Z/ln Z est isomorphe à Z/( i=1 li )Z.

La complexité totale de l’algorithme est O(ln8 q).

4.3 Le critère de Pocklington

Qn e
Théorème 55. Soit N ∈ N∗ . Notons N − 1 = j=1 pj j la décomposition de
N − 1 en facteurs premiers. S’il existe un entier a et i ∈ |[1, n]| tels que :

aN −1 ≡ 1 (mod N ) et (a(N −1)/pi − 1) ∧ N = 1 (16)

alors : d|N ⇒ d ≡ 1 (mod pei i ).

Démonstration. Comme tout facteur d de N est le produit de nombre premiers
(éventuellement d’un seul nombre premier), il suffira de démontrer le théorème
pour tout facteur premier q de N .
On a : aN −1 ≡ 1 (mod N ) donc aN −1 est inversible dans Z/N Z, soit aN −1 ∧N =
1. Or q|N , donc aN −1 ∧ q = 1. q étant supposé premier, on en déduit, d’après
le petit théorème de Fermat : aq−1 ≡ 1 (mod q). Notons o l’ordre de a modulo
q. La relation précédente implique : o|q − 1.
D’autre part, (a(N −1)/pi −1)∧N = 1 donc (a(N −1)/pi −1)∧q = 1 (car q|N ) donc
a(N −1)/pi − 1 ≡ 1 (mod q) donc a(N −1)/pi ≡ 2 6≡ 1 (mod q). Les hypothèses
impliquent donc :

aN −1 ≡ 1 (mod q) n n
)
ej e
Y Y
ei ei −1
⇒ o|p i p j et o 6 |p i pj j
a(N −1)/pi 6≡ 1 (mod q) j=1 j=1
j6=1 j6=1
n
e
Y
⇒ ∃(α, β) ∈ (N∗ )2 , oα = pei i M et oβ 6= piei −1 M avec M = pj j
j=1
j6=1

⇒ ∃(α, β) ∈ (N∗ )2 , pei i |oα et pei i 6 |oβ

⇒ pei i |o

Finalement, on a : pei i |o et o|q − 1. Donc pei i |q − 1, soit q − 1 ≡ 0 (mod pei i ).

D’où q ≡ 1 (mod pei i ).
Corollaire 56 (Critère de Pocklington-Lehmer). Si il existe (F, U ) ∈ N2 tel
que :
1. N − 1 = F U

16
 2. F ∧ U = 1
√
3. F > N − 1
et pour tout facteur premier pi de F , il existe api tel que :

aN
pi
−1
≡ 1 (mod N ) et (ap(N
i
−1)/pi
− 1) ∧ N = 1 (17)

alors N est premier.

Démonstration. D’après le théorème 55, l’hypothèse (17) étant suposée vérifiée,
tout facteur de N est congru à 1 modulo F . Les√facteurs de N dont donc de la
forme αF + 1 (avec α ∈√N∗ ). Or, comme F > N − 1 tout facteur de N est
strictement supérieur à N . Donc N est premier.
Corollaire 57 (Critère de Pocklington). Le critère de Pocklington est le critère
de Pocklington-Lehmer dans le cas particulier où F est un facteur premier de
(N − 1).
Remarque 58. L’hypothèse 2. du critère de Pocklington-Lehmer est alors tou-
jours vérifiée.

4.4 Le critère de Goldwasser-Kilian dans Z/nZ

“Transposons” le critère de Pocklington aux coubes elliptiques.
Soit N un entier dont on veut tester la primalité. Des tests simples (calculs
de congruences par exemple) peuvent nous permettre de nous assurer que N
n’est divisible ni par 2, ni par 3. On peut donc restreindre notre étude à une
courbe elliptique définie sur un corps de caractéristique différente de 2 et 3. Soit
(E, +) : y 2 = x3 + ax + b ∪ O une telle courbe elliptique munie de la structure de
groupe définie par le corollaire 15. Adaptons alors le test de Pocklington dans
(Z/N Z, ×) à (E, +) où E est définie sur le corps (Z/N Z, +, ×).

(Z/nZ\{0}, ×) (E, +)
éléments |[1, N − 1]| {(x, y) ∈ (Z/N Z) | y 2 = x3 + ax + b} ∪ O
lci . +
neutre 1 O √
cardinalité N −1 #E avec |#E − (N + 1)| ≤ 2 N

La condition aN −1 ≡ 1 (mod N ) s’écrit alors : #E · P = O ; la condition

(a(N −1)/q − 1) ∧ N = 1 équivalente à a(N −1)/q 6≡ 1 (mod N ) devient #E
q P 6= O.
√ √
La condition q√> N − 1 signifie : ∀p < N , q > p. Ce qui, transposée à (E, +)
devient ∀p < N , q > #Ep où #Ep est la cardinalité de E modulo p. Or d’après
√ √
le théorème de Hasse (théorème 19), #E ≤ p+1+2 p = ( p+1)2 ≤ (N 1/4 +1)2 .
La condition q > (N 1/4 + 1)2 suffit donc.

17
 5 Notre implémentation
5.1 Détails de la mise en œuvre
Pour les variables numériques, nous n’utiliserons pas le type int limité à 32
bits (soit au maximum 8589934591) mais le type largeint qui nous permet de
manipuler des entiers de taille quelconque.

5.1.1 La classe ec point

On va travailler avec la courbe elliptique : E : y 2 ≡ x3 + ax + b (mod p) ∪ O
avec p 6= 2 et p 6= 3. Les variables correspondantes largeint a, b, p sont
définies globalement. On définit alors la classe ec point dans laquelle on va
implémenter les opérations dans la courbe elliptique :
1 class ec_point
{
public:
largeint x;
5 largeint y;
bool Infty;

ec_point() {Infty = false;};

ec_point(largeint X, largeint Y) {x = X; y = Y; Infty = false;};
10 ec_point(bool isO) {Infty = isO;};
~ec_point() {};
void Print();

void operator = (ec_point P) {x = P.x; y = P.y; Infty = [Link];};

15 friend bool operator == (ec_point P1, ec_point P2);
friend ec_point operator + (ec_point P1, ec_point P2);
friend ec_point operator * (largeint m, ec_point P);
friend ec_point operator * (int m, ec_point P);
};

La variable booléenne Infty vaut true si le point est O ; sinon le point est défini
par ses coordonnées x et y. L’élément neutre O est donc défini par :
#define O_neutre ec_point(true)

On implémente ensuite l’addition de groupe par transcription directe du

corollaire 15.
1 ec_point operator + (ec_point P1, ec_point P2)
{
ec_point P3;
largeint lambda;
5
if ([Link])
P3 = P2;
else if ([Link])
P3 = P1;
10 else if (P1.x == P2.x && P1.y == mod (-P2.y, p))
[Link] = true;
else
{

18
 if (P1 == P2)
15 {
if (gcd(P1.y, p) != 1)
{
//Lambda n’est pas inversible !
error_factor = P1.y;
20 error = true;
}
lambda = mod((3 * P1.x * P1.x + a) * invModN(2 * P1.y, p), p);
}
else
25 {
if (gcd(P2.x - P1.x, p) != 1)
{
//Lambda n’est pas inversible !
error_factor = P2.x - P1.x;
30 error = true;
}
lambda = mod((P2.y - P1.y) * invModN(P2.x - P1.x, p), p);
}
P3.x = mod((lambda * lambda - P1.x - P2.x), p);
35 P3.y = mod((lambda * (P1.x - P3.x) - P1.y), p);
}
return P3;
}

5.1.2 Calcul de kP
L’algorithme utilisé est une adaptation de l’algorithme classique d’exponen-
(2)
tiation rapide. L’idée principale
Pn en est que si k = kn kn−1 . . . k1 k0 est l’écriture
en base 2 de k alors kP = i=0 ki (2i P ). Elle permet de calculer kP avec O(ln n)
opérations au lieu de O(n) pour l’addition naı̈ve. Voici son implémentation pra-
tique :
1 ec_point fast_scalarmult (largeint m, ec_point P)
{
ec_point tmpP, retP;

5 retP = O_neutre;
tmpP = P;
while (m != 0)
{
if(error) //Lambda n’etait pas inversible !
10 return O_neutre;
if(getbit(m, 0)) //Le bit de poids le plus faible est il non nul ?
retP = retP + tmpP;
m >> 1; //Decalage de 1 bit vers la gauche
tmpP = 2 * tmpP;
15 }

return retP;
}

19
 5.1.3 Calcul des inverses
Lors du calcul de λ, l’inverse de (x2 − x1 ) ou de 2y1 modulo n est calculé
à l’aide de l’algorithme d’Euclide étendu qui permet de calculer les coefficients
de Bezout. Il est basé sur l’identité fontamentale de l’algorithme d’Euclide sui-
vante :
d = a ∧ b = b ∧ (a mod b) (18)
Démonstration. Montrons (bq + r) ∧ b = b ∧ r. Soit d = (bq + r) ∧ b et d′ = b ∧ r.
On a : d|bq + r et d|b donc d|r d’où d|r = (bq + r) − bq donc d|d′ .
De plus : d′ |b donc d′ |bq et d′ |r donc d′ |bq + r d’où d′ |d.
Finalement, on a bien d = d′ .

Ceci implique que si d = bx + (a mod b)y ′ alors d = ax + by avec x = y ′ et

y = x′ − ⌊a/b⌋y ′.
Démonstration. On a en effet d’après le théorème de Bezout et l’égalité (18) :

d = bx′ + (a mod b)y ′

= bx′ + (a − ⌊a/b⌋b)y ′
= ay ′ + b(x′ − ⌊a/b⌋y ′ )

On a de plus la condition d’arrêt de l’algorithme en posant

d=a∧0=a∧1=a

1 struct couple
{
largeint x;
largeint y;
5 };

couple Bezout(largeint a, largeint n)

{
couple cRet;
10 largeint tmp;

if (b == 0)
{
cRet.x = 1;
15 cRet.y = 0;
return cRet;
}
cRet = Bezout(b, mod(a, b));
tmp = cRet.y;
20 cRet.y = cRet.x - (a / b) * cRet.y;
cRet.x = tmp;
return cRet;
}

25 largeint invModN(largeint a, largeint n)

20
 {
return mod((Bezout(a, n)).x, n);
}

5.1.4 Le ppcm(1, 2, . . . , B)
Pour des raisons de rapidité, dans la pratique, on ne prend pas k = ppcm(1, 2, . . . , B)
mais k = ppcm(B, B − 1) :

1 largeint calc_k(largeint B)
{
return lcm(B, B - 1);
}

5.1.5 La procédure principale

On va travailler sur les courbes elliptiques E : y 2 ≡ x3 + ax + b (mod n) ∪ O.
Le coefficient a étant fixé (c’est notre paramètre), on choisit b de sorte que
P = (1, 1) appartienne à E : b = 12 − 13 − a × 1 = −a. On calcule alors kP pour
nb essais valeurs de a, puis on invcrémente B et on recommence jusqu’à ce
que λ ne soit pas inversible dans le calcul de kP ce qui est signalé par la valeur
true de la variable booléenne error. La variable error factor contient alors
la valeur du nombre qui n’a pas été inversible lors du calcul de λ.

1 #define B_incr 1
#define a_incr 30
#define nb_essais 40
#define x_init 1
5 #define y_init 1

largeint TrouveFacteur(largeint n, largeint B)

{
ec_point P, Q;
10 largeint k, tmp;
int a_essais;
bool nouvelle_courbe=false;

error = false;
15 if ((n % 2) == 0)
{
//Le facteur 2 a ete trouve
//...
return largeint(2);
20 }
if ((n % 3) == 0)
{
//Le facteur 3 a ete trouve
//...
25 return largeint(3);
}

p = n;
k = calc_k(B);
30 b = 1;

21
 a = 1; a_essais = 0;

P.x = x_init; P.y = y_init;

while (1)
35 {
b = (P.y * P.y) - (P.x * P.x * P.x) - (a * P.x);

//PGCD(Delta, n) == 1 ?
tmp = gcd(4 * a * a * a + 27 * b * b, n);
40 while (tmp != 1)
{
if (tmp == n)
{
a += a_incr;
45 b = (P.y * P.y) - (P.x * P.x * P.x) - (a * P.x);
tmp = gcd(4 * a * a * a + 27 * b * b, n);
}
else
return tmp;
50 }
if (a_essais > nb_essais)
nouvelle_courbe = true;
Q = k * P;
//Lambda n’etait-il pas inversible ?
55 if (error)
{
largeint g = gcd(error_factor, n);

if(1 < g && g < n)

60 {
//Impression des resultats
//...
return g;
}
65 else
nouvelle_courbe = true;
}
//On change de courbe
if (nouvelle_courbe)
70 {
a = 1;
a_essais = 0;
B += B_incr;
while (k == calc_k(B)) {B += B_incr;};
75 k = calc_k(B);
}
else
//On incremente a
{
80 a += a_incr;
a_essais++;
}
}

22
85 //Cette commande n’est jamais executee
return largeint(1);
}

5.2 Résultats
Voici quelques résultats renvoyés par notre programme. Il est à noter que le
dernier facteur n’est jamais “trouvé” ; il faudrait pour cela implémenter un test
de primalité. Ces tests on été effectués sous Windows 2000 sur un Pentium 4
cadencé à 1, 5 GHz et doté de 256 Mo de RAM.

5.2.1 109849677793909 = 239633 · 11131 · 41183

Nombre a factoriser : 109849677793909
B-lissite : 10487395

10:58:58

10:58:58
facteur : 11131
a : 151
b : -151
p : 109849677793909
B : 10487395
k : 109985443398630

10:58:59
facteur : 41183
a : 571
b : -571
p : 9868805839
B : 10487395
k : 109985443398630

5.2.2 2974015455045701710807 = 206083 · 64849 · 34729 · 6407749

Nombre a factoriser : 2974015455045701710807
B-lissite : 54535001572

11:05:03

11:05:06
facteur : 34729
a : 511
b : -511
p : 2974015455045701710807
B : 54535001572
k : 2974066396403507469612

11:05:20
facteur : 206083
a : 1
b : -1
p : 85634929167142783

23
B : 54535001634
k : 2974066403165847668322

11:06:08
facteur : 64849
a : 1
b : -1
p : 415536114901
B : 54535001634
k : 2974066455192239454210

5.2.3 19480333860937071253 = 1562513 · 6512647 · 1914323

Nombre a factoriser : 19480333860937071253
B-lissite : 4413785992

11:08:06

11:11:27
facteur : 6512647
a : 1
b : -1
p : 19480333860937071253
B : 4413789312
k : 19481536086311644032

11:13:28
facteur : 1562513
a : 1
b : -1
p : 2991154573699
B : 4413792774
k : 19481566647400822302

5.2.4 134755010254579987971511 = 61494437 · 42398497 · 51684299

Nombre a factoriser : 134755010254579987971511
B-lissite : 367091132971

18:47:46

19:03:32
facteur : 42398497
a : 1
b : -1
p : 134755010254579987971511
B : 367091143560
k : 134755907679821438330040

5.2.5 Limites de l’implémentation

La gestion de la mémoire n’est pas optimale (ceci est lié à l’utilisation de
la classe largeint) ; en effet la mémoire allouée pour les largeint (en parti-
culier pour les ec point) n’est désallouée qu’à la toute fin du programme. Au

24
bout d’un dizaine de minute la mémoire de l’ordinateur est saturée et le pro-
gramme plante. C’est pourquoi dans la pratique nous n’avons pas pû réaliser de
factorisation de nombre ayant des facteurs premiers de plus de 8 chiffres.
Une technique pour résoudre ce problème consisterait à untiliser des smart
pointers qui sont des pointeurs dont on a surchargé l’opérateur ->, ce qui permet
de tenir en permanence un compte du nombre de références au pointeur et d’en
appeler le destructeur (donc de libérer la mémoire qui lui a été allouée) lorsque
ce nombre devient nul.
Bien d’autres optimisations sont possibles ; en particulier “linéariser” le code
en enlevant les classes au détriment de la facilité de mise en œuvre et de la clarté
du code.

Bibliographie
[1] Thomas Cormen, Charles Leiserson, Ronald Rivest. Introduction à
l’algorithmique. Dunod, 1994.
[2] Johannes Buchmann. La factorisation des grands nombres. Pour la
science, (251) : pages 88–96, septembre 1998.
[3] François Arnault. Théorie des nombres et cryptographie. Cours de
DEA, Université de Limoges, mars 2000.
[Link]
[4] Site de Certicom.
[Link]
[5] Marc Joye. Une introduction élémentaire à la théorie des courbes
elliptiques. Technical report, Université catholique de Louvain, juin
1995.
[Link]
[6] Reynald Lercier. Algorithmique des courbes elliptiques dans les corps
finis. Thèse, LIX – CNRS, juin 1997.
[Link]
[7] Douglas Stinson. Cryptographie – Théorie et pratique, chapı̂tre 5,
pages 159–170. International Thomson publishing, 1995.

Réalisé à l’aide de LATEX.

25