Wiki du cours

Rédacteur: Filipe Moreira Da Silva

A traiter [Modifier]

(On suivra principalement [1].)

• Définition alternative du couplage de Weil (sans preuve).
• Choix naturel des diviseurs.
• Idée: calcul par doublages successifs sur \( n \).
• Formule (11.9), permettant de calculer le couplage pour \( n = j + k \) à partir du couplage pour \( n = j \) et \( n = k \).
• Algorithme de Miller

Définition alternative du couplage de Weil: [Modifier]

Une définition alternative est donnée par le théorème ci-dessous:

Théorème : Soient \(S,T\in E[n]\). Soient \(D_S\) et \(D_T\) des diviseurs de degré 0 tels que
\(Sum(D_S) = S\) et \(Sum(D_T) = T\)
et tels que \(D_S\) et \(D_T\) n'ont pas de points en commun. Soient \(f_s\) et \(f_t\) des fonctions telles que
\(div(f_S) = nD_S\) et \(div(f_T) = nD_T\).
Alors le couplage de Weil est donné par
\(e_n(S,T) = \frac{f_T(D_S)} {f_S(D_T)}\)

Choix naturel des diviseurs: [Modifier]

Un choix naturel de diviseur est:
\(D_S = [S] - [\infty], D_T = [T+R] - [R]\)
pour un point \(R\) choisi aléatoirement. On a alors,
\(e_n(S,T)\) = \(\frac{ f_S(R)f_T(S)} {f_S(T+R)f_T(\infty)}\)

Calcul par doublage successif sur n: [Modifier]

Soit \(n\) un entier positif et \(P\) un point de la courbe elliptique donnée. Le calcul par doublage successif permettant de calculer \(nP\) est donné par les quatre étapes ci-dessous :

1. On commence avec \(a=n\), \( B= \infty\) et \(C=P\)
2. Si a est pair, on pose \(a= \frac{a}{2}\), \(B=B\) et \(C= 2C\)
3. Si a est impair, on pose \(a=a-1\), \(B=B+C\), \(C=C\)
4. Si \(a \ne 0\), on retourne à la deuxième étape.
5. Exprimer \(B\)

La valeur \(B\) sera \(nP\)

Formule (11.9), permettant de calculer le couplage pour \( n = j + k \) à partir du couplage pour \( n = j \) et \( n = k \): [Modifier]

On veut utiliser la méthode de calcul par doublage successif pour arriver à \( n= j+k \). Mais les diviseurs j[P+R] - j[R] pour j<n ne sont pas des diviseurs de fonctions. Alors, on introduit les diviseurs suivant :
\(D_j\)= j[P+R] - j[R] -[jP] + \([\infty]\). Avec \(P\in E[n]\) et \(R\in E\).
Alors, \(D_j\) est un diviseur d'une fonction, et par le théorème 11.2 il existe \( f_j \) telle que:
\(div(f_j)\)=\(D_j\).
On suppose que \(\frac{f_j(Q_1)}{f_j(Q_2)}\) et \(\frac{f_k(Q_1)}{f_k(Q_2)}\) ont déjà été calculé. On va voir comment calculer \(\frac{f_{j+k}(Q_1)}{f_{j+k}(Q_2)}\)
Soit ax+by+c=0 la droite passant par jP et kP (la tangente si jP=kP), on a vu dans le sujet 8 que \(div(ax+by+c)\) = [jP] + [kP] - [-(j+k)P] - 3\([\infty]\).
Soit x+d=0 la droite verticale passant par (j+k)P et -(j+k)P, on a également vu dans le sujet 8 que \(div(x+d)\) = [(j+k)P]+ [-(j+k)P] - 2\([\infty]\). Alors,
\(div(\frac{ax+by+c}{x+d})\) = \(div(ax+by+c)\) - \(div(x+d)\) = [jP] + [kP] - [(j+k)P] - \([\infty]\).
On a donc: \(div(f_{j+k})\)= \(D_{j+k} = D_j + D_k \)+ \(div(\frac{ax+by+c}{x+d})\) = \(div(f_jf_k\frac{ax+by+c}{x+d})\).
C'est-à-dire qu'il existe une constante \(\gamma\) telle que:
\(f_{j+k}\)= \(\gamma f_jf_k\)\(\frac{ax+by+c}{x+d}\).
On obtient alors, la formule (11.9):
\(\frac{f_{j+k}(Q_1)}{f_{j+k}(Q_2)}\) = \(\frac{f_{j}(Q_1)}{f_{j}(Q_2)}\)\(\frac{f_{k}(Q_1)}{f_{k}(Q_2)}\)\(\frac{(ax+by+c)/(x+d)|_{(x,y)=Q_1}}{(ax+by+c)/(x+d)|_{(x,y)=Q_2}}\)

Cette méthode permet de calculer \(f_{j+k}\) grâce à \(f_j\) et \(f_k\) assez rapidement. Par exemple, si on connait \(\frac{f_j(Q_1)}{f_j(Q_2)}\) pour j = \(2^i\), on peut calculer rapidement la même expression pour j=\(2^{i+1}\) et refaire de même pour des puissances plus grandes ou les additionner pour des valeurs quand j est une somme de puissance carré. C'est ce qu'il arrive quand on fait un calcul par doublage successif pour arrivé jusqu'à n.
On peut alors calculer \(\frac{f_n(Q_1)}{f_n(Q_2)}\) rapidement. Mais, quand j=n on a:
\(div(f_n)\) = n[P+R] - n[R] + [nP] +\([\infty]\) = n[P+R] - n[R] car [nP] = \([\infty]\). On a alors que \(f_n\) est la fonction f, et donc, on a terminé notre calcul.

Cette méthode est utilisée dans l'algorithme ci-dessous.

Algorithme de Miller [Modifier]

Soit \(P\in E[n]\) et soient R, \(Q_1, Q_2\) des points de E. Soit \(f_j\) tel que \(div(f_j)= D_j\). On définit:
\(v_j = \frac{f_j(Q_1)}{f_j(Q_2)}\)
la valeur de \([f_j]\) sur le diviseur \([Q_1] - [Q_2]\)

1. On commence avec \(i=n, j=0\) et k=1. Soit \(f_0\)=1 et on calcule \(f_1\) à l'aide de \(f_0\), de la formule (11.9) et du diviseur [P+R] - [P] - [R] + \([\infty]\)

2.Si i est pair, on pose \(i=\frac{i}{2}\) et on calcule \(v_{2k} = \frac{f_{2k}(Q_1)}{f_{2k}(Q_2)}\) en termes de \(v_k\), en utilisant la formule (11.9). On remplace k par 2k, mais on garde le même j. On sauvegarde la paire \((v_j,v_k)\) pour la nouvelle valeur de k.

3. Si i est impair, on pose \(i=i-1\), et on calcule \(v_{j+k}\) = \(\frac{f_{j+k}(Q_1)}{f_{j+k}(Q_2)}\) en termes de \(v_j\) et \(v_k\), en utilisant la formule (11.9). On remplace j par j+k, mais on garde le même k. On sauvegarde la paire \((v_j,v_k)\) pour la nouvelle valeur de k.

4. Si \(i \ne 0\), on retourne à la deuxième étape.

5. Retourner \(v_j\)

Cette valeur sera \(v_n = \frac{f_n(Q_1)}{f_n(Q_2)}\)

Références [Modifier]

[1] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Section 11.4.
[2] Craig Costello, Pairings for beginners, Section 5.3