FACTORISATION DES ENTIERS PAR LA MÉTHODE DES COURBES ELLIPTIQUES

FACTORISATION DES ENTIERS PAR LA MÉTHODE DES COURBES ELLIPTIQUES

 Courbes elliptiques

Les courbes elliptiques sont des courbes particulières, sur lesquelles on peut définir une arithmétique. Elles ont des applications en théorie des nombres ainsi qu’en cryptographie. Pour définir la loi de groupe, on propose ici deux approches differentes : dans un premier paragraphe, on considère les courbes elliptiques comme des objets purement algebrique, puis dans le paragraphe suivant, on prendra le point de vue des équations de Weiertrass, sans oublier de faire le lien entre ces approches. la suite de cette section concernera l’étude des courbes elliptiques sur les corps finis et nous proposerons ensuite une méthode basée sur l’utilisation de ces groupes pour trouver un facteur d’ un entier. Définition 2.1. Une courbe elliptique E sur un corps K de caractéristique différente de 2 et de 3 est une cubique lisse dans le plan projectif P 2 (K). L’ensemble des points de la courbe peut alors être muni d’une structure de groupe .

Structure de groupe

L’ensemble des points d’une courbe elliptique comme nous allons le voir dans ce qui suit, peut être muni d’une loi de groupe commutative et cette loi de composition interne sera notée de manière additive et nous permettra de définir la multiplication d’un point par un nombre entier. Nous disposerons alors du matériel nécessaire pour introduire le problème de la factorisation. Additionner des points : définition par la méthode de la sécante-tangente Dans tout ce qui suit E désignera une courbe elliptique sur un corps K. On veut des points rationnels. Remarque 2.2. Du point de vue géométrique il est facile d’obtenir ces points rationnels. Soient P, Q deux points de E et (D) la droite passant par P et Q. L’addition de ces deux points est rendue possible par la propriété suivante, qui est un cas particulier du théorème de Bézout sur l’intersection de courbes algebriques sur les réels.  Lemme 2.3. Soit E une courbe elliptique et D une droite, toutes deux définies sur un corps K. Si la droite D coupe la courbe E en deux points (comptés avec leur multiplicité), alors elle recoupe E en un troisième point (distinct ou non). Nous voyons que cette propriété est un cas particulier du théorème de Bézout. Comme l’équation de E est de degré 3, le théorème de Bézout montre que (D) intercepte la courbe en un troisieme point(comptés avec multiplicités). Remarque 2.4. Nous pouvons constater que sur la figure, une droite verticale coupant la courbe C ne semble pas la couper en un troisième point. Ceci est lié à la difficulté de représenter P 2 sur un plan. Ce troisième point existe bien sûr, il appartient à P 1 , il est appelé point à l’infini et est noté O. De cette propriété, une première loi de composition interne que nous noterons + peut être déduite. Elle servira à construire la loi de groupe sur l’ensemble des points d’une courbe elliptique. Pour déterminer la somme, on suit la procédure suivante : 1. On trace la droite (D) passant par P et Q. 2. (D) coupe alors la courbe E en un troisième point R, non nécessairement distinct de P et Q. 16 3. La droite passant par R et O recoupe la courbe E en un troisième point qui sera P +Q. Notre point P + Q est défini comme étant le troisième point d’intersection de la droite (RO) et E. De plus la loi + est bien interne puisque P +Q est l’intersection d’une droite et de la courbe, c’est donc un point de la courbe E. Remarque 2.5. – Si les points P et Q sont confondus, alors la droite (D), devient la tangente à la courbe en P. – Le fait d’avoir imposer que la courbe soit lisse nous permet d’être sûre que la tangente en P existera toujours. – Si (D) est verticale, alors P + Q = O où O est le point à l’infini. Dans un premier temps la loi de groupe abélien d’une courbe elliptique va être défini d’un point de vue géométrique comme suit. Nous verrons dans la sous section suivante comment la définir en utilisant les coordonnés des points de la courbe. Proposition 2.6. La loi de composition interne + vérifie les propriétées suivantes : a) Si une droite intersecte E en trois points P, Q et R (non nécessairement distincts), alors (P + Q) + R = O b) P + O = O + P = P, pour tout P ∈ E c) P + Q = Q + P, pour tous P, Q ∈ E d) soit P ∈ E il existe un point de E, noté −P, qui satisfait P + (−P) = O. e) soient P, Q et S ∈ E, alors (P + Q) + S = P + (Q + S) En d’autre terme la loi + munit E d’une structure de groupe abélien et associatif avec comme élément neutre O. Démostration : La seule propriété difficile est en fait l’associativité e). a) Puisque la courbe E est de degré trois, alors P, Q et R sont les seuls points d’intersection de E et la droite (P Q). Ainsi donc R est le troisième point d’intersection de celle-ci. Soit S le troisième point d’intersection de E et la droite (RO). Il vient alors S = P + Q. Donc (P +Q) +R = S +R en voyant que O est le troisième point de rencontre de E et (RS) et la tangente à E en O recoupe E en O lui même. On a alors (P + Q) + R = O. 17 b) En prenant Q = O c’est à dire la droite qui coupe la courbe en P, O et R. D’une part la droite passant par R et O recoupe la courbe en P +O. D’autre part puisque (P +O)+R = O la droite passant par R et O recoupe la courbe en P. Il vient alors P + O = P c) La droite passant par P et Q est la même que celle passant par Q et P. Donc P +Q = Q+P d) Soit la droite passant par P et O recoupe la courbe E en R. En utilisant a) on obtient :(P + O) + R = O et puisque P + O = P d’aprés a) on a donc P + R = O e) Une démostration de cette propriété repose sur un résultat de géométrie algébrique, le théorème fondamental de Max Noether. Une conséquence en est le théorème des neuf points : Si la courbe E intersecte deux courbes cubiques C1 et C2 chaque fois en neuf points, et si huit de ces points sont les même pour C1 et C2 alors le neuvième point d’intersection est aussi le même. L’idée de la preuve de l’associativité est alors de fabriquer les deux cubiques C1 et C2 de manière à contrôler huit de leurs points d’intersection avec la courbe elliptique et à s’arranger pour que le neuvième soit l’un des points (P +Q)+R ou P + (Q+R) que l’on veut comparer(ou leurs symétriques par rapport à l’axe des abcisses). Pour cela considérons les points suivant : R0 le troisième point d’intersection de la courbe E avec la droite (P Q) et R1 son symétrique c’est à dire R1 = P + Q. R2 le troisième point d’intersection de E avec la droite (R1R) et R3 son symétrique par rapport à l’axe des abcisses. Donc R3 = (P + Q) + R Avec ce même procédé passons maintenant pour la construction de P + (Q + R). Soit Q0 le troisième point de rencontre de E avec la droite (QR), et Q1 son symétrique par rapport à l’axe des abcisses. Soit Q2 le troisième point d’intersection de E avec la droite (Q1P), et Q3 son symétrique par rapport à l’axe des abcisses. On a alors Q3 = P + (Q + R). On fabrique C1 comme étant la réunin des droites (P Q), (Q0O) et (R, R1), et C2 comme étant la réunion des droites (QR), (R0O) et (P Q1). On a alors E ∩ C1 = {P, Q, R, O, R0, R1, Q0, Q1, R2} E ∩ C2 = {P, Q, R, O, R0, R1, Q0, Q1, Q2} D’aprés le théorème cité, R2 = Q2 et donc leurs symétriques sont les même c’est à dire R3 = Q3. Il vient alors (P + Q) + R = P + (Q + R) (Ea,b(K), +) est donc belle et bien un groupe abélien et associatif  ..