Wiki du cours

Rédacteur: Benjamin Carrel

Addition de points sur une courbe elliptique \(E\) [edit]

Introduction : Problématique

Soit une courbe elliptique \(E\) d'équation \(y^2 = x^3 + Ax + B\) sur un corps \(\mathbb{K}\). Soient deux points \(P_1, P_2 \in E\). On aimerait pouvoir additionner ces deux points, cependant l'addition coordonnée par coordonnée ne donne pas forcément un point sur la courbe. Un moyen d'additionner deux points sur une courbe elliptique \(E\) est la suivante :

1. Tracer la droite \(L\) reliant \(P_1 \) à \(P_2 \).
2. Trouver le troisième point d'intersection \(P_3' \) entre \(L\) et \(E\). (Nous discuterons de l'existence d'un tel point par la suite)
3. Construire \(P_3 \) comme réflection de \(P_3' \) par l'axe des \(x \).
4. On obtient \(P_1 + P_2 = P_3 \)

Voici une illustration de ce procédé dans le cas \(\mathbb{K} = \mathbb{R}\). (Figure 2.2, page 12, cf référence)

Construction algébrique

Traduisons maintenant ces étapes algébriquement.

Soient \(P_1 = (x_1,y_1)\) et \(P_2 = (x_2,y_2)\) distincts.

La pente entre ces deux points est \(m = \frac{y_2-y_1}{x_2-x_1}\).

La droite \(L\) reliant nos deux points a pour équation \(y = m(x-x_1) + y_1\).

En substituant cette forme dans l'équation de notre courbe elliptique, on obtient :

\(y^2 = x^3 + Ax + B \iff (m(x-x_1)+y_1)^2 = x^3 + Ax + B \iff 0 = x^3 - m^2x^2 + ...\)

On a donc un polynôme de degré 3. Puisqu'on cherche les points d'intersections entre \(E\) et \(L\), on cherche les racines de ce polynôme. Heureusement, on connaît déjà deux points d'intersection, donc deux racines : \(x_1\) et \(x_2\).

Rappelons qu'en factorisant on a : \(x^3 + ax^2 + bx + c = (x-r_1)(x-r_2)(x-r_3) = x^3 - (r_1+r_2+r_3) x^2 + ... \Rightarrow a = -(r_1+r_2+r_3)\).

Donc dans notre cas on obtient \(-m^2 = -(x_1 + x_2 + x_3) \Rightarrow x_3 = m^2 - x_2 - x_1\) ce qui donne la première coordonnée de \(P_3\). La deuxième coordonnée \(y_3\) est obtenue par la négation de l'équation précédente pour obtenir la réflection par l'axe des \(x\).

Conclusion : \(P_3 = (x_3,y_3)\) avec \(x_3 = m^2 - x_2 - x_1\) et \(y_3 = m(x_1 - x_3) - y_1\).

• Si \(P_2 = \infty\), la droite \(L\) reliant \(P_1\) à \(P_2\) est verticale. Dans ce cas, l'intersection avec la courbe \(E\) est le point \(P_1'\) qui est la réflection de \(P_1\) par l'axe des \(x\). Après réflection, on obtient de nouveau \(P_1\), donc \(P_1 + \infty = P_1\). (Si ce n'est pas clair, c'est évident avec un dessin)

Cas \( x_1 = x_2 \)

Dans ce cas, la pente \(m=\infty\) et la droite \(L\) est verticale. L'intersection entre \(L\) et \(E\) se fait à l'infini, qui reste l'infini après réflection par l'axe des \(x\). Dans ce cas, on définit donc \(P_1 + P_2 = \infty\)

Cas \( P_1 = P_2 \)

La construction précédente n'est valable que si \(P_1\) et \(P_2\) sont distincts.

Si \(P_1 = P_2 = (x_1,y_1)\), la droite \(L\) peut-être vue comme la tangente à la courbe \(E\) en ce point.
Avec cette approche, la pente de \(L\) est donnée par l'équation dérivée, c'est à dire : \((2y_1) dy = (3x_1^2 + A) dx\) donc \(m = \frac{dy}{dx} = \frac{3x_1^2 + A}{2y_1}\).

• Si le dénominateur \(y_1 = 0\), alors le numérateur \(3x_1^2 + A \neq 0\) (cf Sujet 2), on a donc \(m = \infty\) et \(L\) est verticale. Dans ce cas, on définit \(P_1 + P_2 = P_1 + P_1 = \infty\).

• Si \(y_1 \neq 0\), alors \(L\) a pour équation \(y = m(x-x_1)+y_1\). Comme précédemment, on a le polynôme \(0 = x^3 - m^2x^2 + ...\), dont on connaît la racine double \(x_1\). On obtient \(P_3 = (x_3,y_3)\) avec \(x_3 = m^2 - 2x_1\) et \(y_3 = m(x_1-x_3) - y_1\)

Recapitulatif : On utilisant les notations \(P_i = (x_i,y_i)\) on calcule \(P_1 + P_2 = P_3\) ainsi :

• Si \(x_1 \neq x_2\), alors \(x_3 = m^2-x_1-x_2\) et \(y_3 = m(x_1-x_3) - y_1\) avec \(m = \frac{y_2-y_1}{x_2-x_1}\)
• Si \(x_1 = x_2\) et \(y_1 \neq y_2\), alors \(P_1 + P_2 = \infty\)
• Si \(P_1=P_2\) et \(y_1 \neq 0\), alors \(x_3 = m^2-2x_1\) et \(y_3 = m(x_1-x_3) - y_1\) avec \(m = \frac{3x_1^2 + A}{2y_1}\)
• Si \(P_1 = P_2\) et \(y_1 = 0 \), alors \(P_1 + P_2 = P_1 + P_1 = \infty\)

Propriétés de l'addition: loi de groupe [edit]

Théorème

\((E,+)\) est un groupe abélien avec pour élément neutre \(\infty\). C'est à dire :

1. (Elément neutre) \(P + \infty = P, \forall P \in E\)
2. (Commutativité) \(P_1 + P_2 = P_2 + P_1, \forall P_1,P_2 \in E\)
3. (Elément inverse) \(\forall P \in E, \exists P' \in E\) tel que \(P + P' = \infty\). On notera \(P' = -P\).
4. (Associativité) \((P_1 + P_2) + P_3 = P_1 + (P_2 + P_3) \forall P_1,P_2,P_3 \in E\)

Preuve

1. On a \(P + \infty = P\) par construction. (cf dernier point avant le récapitulatif)
2. La commutativité est directe car la droite reliant \(P_1\) à \(P_2\) est la même que celle reliant \(P_2\) à \(P_1\), et donc par construction on a bien \(P_1 + P_2 = P_2 + P_1\).
3. Pour l'élément inverse, soit \(P \in E\). Soit \(P' \in E\) la réflection de \(P\) par l'axe des \(x\). La droite reliant \(P\) à \(P'\) est verticale donc \(P+P' = \infty\).
4. La preuve de l'associativité n'est pas demandée. Celle-ci se fait par calcule direct, ce qui est assez long et sans grand intérêt. Une autre approche est aussi possible, cf Section 2.4 de la référence pour les intéressés. CQFD

Exemples [edit]

• Soit la courbe elliptique \(E\) d'équation \(y^2 = x^3 - 25x\) avec \(\mathbb{K} = \mathbb{R}\).

On a \(A = 25, B= 0\). Soit \(P = (-4,6)\). Calculons \(2 * P = 2 * (-4,6) = (-4,6) + (-4,6)\)
Commençons par calculer \(m = \frac{3x^2 + A}{2y} = \frac{3*(-4)^2 + (-25)}{2*6} = \frac{23}{12}\).
On a donc \(x_3 = m^2 -2x = \frac{23}{12}^2 - 2*(-4) = \frac{1681}{144}\) et \(y_3 = m(x-x_3) - y = \frac{23}{12}*(-4-\frac{1681}{144})-6 = -\frac{62279}{1728}\)
On trouve \(2 * P = 2 * (-4,6) = (-4,6) + (-4,6) = (\frac{1681}{144},-\frac{62279}{1728})\).

Si maintenant on veut calculer \((0,0) + (-5,0)\), on calcule \(m = \frac{y_2-y_1}{x_2-x_1} = \frac{0}{-5}\).
On a donc \(x_3 = m^2 - x_1 - x_2 = 0 - 0 - (-5) = 5\) et \(y_3 = m(x_1-x_3)-y_1 = 0*(0-5)-0 = 0\).
On trouve \((0,0) + (-5,0) = (5,0)\)
On peut trouver directement par définition : \(2(0,0)=2(-5,0)=2(5,0)=\infty\).

• Soit la courbe elliptique \(E\) d'équation \(y^2 = x^3 - x\) avec le corps finis \(\mathbb{K} = \mathbb{Z_3}\).

Considérons les points \(P_1 = (1,0)\) et \(P_2 = (2,0)\) (On peut facilement vérifier que ces points vérifient l'équation de \(E\) dans le corps \( \mathbb{Z_3}\).
Calculons \(P_1 + P_2\).
On a \(m = \frac{y_2-y_1}{x_2-x_1} = \frac{0}{1} = 0\) donc \(x_3 = m^2 - x_1 - x_2 = 0 - 1 - 2 = -3 = 0\) et \(y_3 = m(x_1-x_3)-y_1 = 0* (1-0) - 0) = 0\).
On a donc trouvé \(P_1 + P_2 = P_3 = (0,0)\).

Important : A première vue cet exemple peut sembler un peu simpliste. Mais ce qu'on peut y observer est très intéressant !
En effet, sur un corps finis le nombre de points est finis. De plus, par le théorème vu précédemment, le groupe formé par ces points avec l'opération d'addition est un groupe abélien ! Exercice intéressant : Observer cet exemple et réfléchir à sa structure abélienne.
Pour rappel, les groupes abéliens ont des propriétés intéressantes, et ces propriétés seront la base des applications en crytographie des courbes elliptiques sur des corps finis que nous verrons plus tard !

• Un dernier exemple est donné pour les courbes elliptiques sur \(\mathbb{C}\) et sera présenté dans le sujet suivant.

Références [edit]

[1] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Section 2.2.