Calcul d’isogénies entre courbes elliptiques

Introduction au domaine de recherche

Jean Kieffer

16 octobre 2017

Table des matières

1 Courbes elliptiques et isogénies 2

2 Calcul d’isogénies 3
2.1 Un peu d’histoire. . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Les formules de Vélu. . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 La méthode de Stark. . . . . . . . . . . . . . . . . . . . . . . 5
2.4 La méthode d’Elkies. . . . . . . . . . . . . . . . . . . . . . . . 6
2.5 L’algorithme de Couveignes. . . . . . . . . . . . . . . . . . . . 8

3 Application au comptage de points 9

Introduction
Une isogénie est un morphisme surjectif et de noyau fini entre variétés
abéliennes. Ce sont des objets fondamentaux dans l’étude de ces variétés,
et donc des courbes algébriques en général. Dans ce document, on parlera
plus spécifiquement de courbes elliptiques, qui sont des variétés abéliennes de
dimension 1 ; les isogénies sont les flèches non triviales dans la catégorie des
courbes elliptiques sur un corps k donné, et ce sont des quasi-isomorphismes
dans un certain sens.
Les isogénies sont aussi étroitement liées aux sous-groupes de torsion
sur les courbes elliptiques. Un sous-groupe fini d’une courbe elliptique est
toujours le noyau d’une isogénie, déterminée à isomorphisme près, et il est
souvent intéressant de travailler avec celle-ci.
Vu ces liens profonds avec les sous-groupes de torsion d’une courbe et leur
rôle de quasi-isomorphisme, les isogénies sont des objets centraux lorsque l’on
regarde des représentations de Galois attachées aux courbes, des questions
de modularité, ou les questions liées à la conjecture de Birch et Swinnerton-
Dyer : en un mot, dans toutes les situations où l’on regarde les courbes

1
elliptiques comme plus qu’un simple groupe de points. Savoir calculer avec
des isogénies est alors essentiel pour faire quoi que ce soit.

Ce document est organisé comme suit. Dans un premier temps, on expose

le matériel nécessaire (courbes elliptiques et isogénies), et on présente en-
suite différentes méthodes pour le calcul d’isogénies (des algorithmes, donc).
Enfin on s’intéresse à une application au comptage de points d’une courbe
elliptique sur un corps fini.

1 Courbes elliptiques et isogénies

Soit k un corps. Une courbe elliptique E sur k est une courbe algébrique
projective, lisse, de genre 1 munie d’un point rationnel fixé 0E . Par exemple,
la courbe plane projective donnée sous forme de Weierstrass (réduite)
y 2 = x3 + ax + b, où a, b ∈ k et 4a3 − 27b2 6= 0
munie du point fixé (0 : 1 : 0), est une courbe elliptique. On peut en fait
montrer qu’en dehors des caractéristiques 2 et 3, toute courbe elliptique
admet une équation de ce type. Si E est sous forme de Weierstrass comme
ci-dessus, on peut la munir d’une forme différentielle sans zéros ni pôles :
dx
ωE = .
y
Toutes les autres telles formes différentielles sont des multiples de ωE : c’est
ce que signifie être une courbe de genre 1.
Une propriété essentielle est que l’ensemble E(K) des points de E sur
tout corps K extension de k est un groupe abélien d’élément neutre le point
marqué. Trois points alignés sont de somme nulle ; on peut utiliser cette
propriété pour donner des formules explicites de cette loi de groupe dans les
coordonnées x, y.

Une isogénie est un morphisme non nul φ : E → E 0 entre courbes ellip-

tiques. C’est un morphisme de groupes, mais aussi une application régulière,
donnée par des fractions rationnelles en x, y : on appelle degré de l’isogénie le
degré de ces fractions. C’est aussi, en général (dans le cas séparable, auquel
on se restreint dans ce document) le nombre de préimages de chaque point :
ainsi, le noyau d’une isogénie de degré ` sera un sous-groupe de cardinal `.
Le pullback φ∗ ωE0 est un multiple de ω : on en déduit qu’il existe un certain
E
c et une fraction rationnelle φx tels que
φ(x, y) = (φx (x), cyφ0x (x)).
Les endomorphismes de E sont les isogénies de E vers E, plus 0. Par
exemple, les multiplications scalaires pour m ∈ Z
[m]E : P 7→ P + · · · + P, m fois

2
sont des endomorphismes. L’isogénie [m] est de degré m2 , et son noyau est
noté E[m], le sous-groupe des points de m-torsion de la courbe. En utilisant
la loi de groupe, on peut calculer explicitement un polynôme de degré m2 −1
s’annulant sur les points de E[m], le polynôme de m-division de E.
Cela donne une copie de Z à l’intérieur de End(E). Ce ne sont pas
toujours les seuls endomorphismes, et même jamais lorsque k est un corps
fini de cardinal q : le morphisme de Frobenius

πE : (x, y) 7→ (xq , y q )

est un endomorphisme qui n’est pas une multiplication scalaire 1 .

Si E est une courbe elliptique sur C, on montre que E est isomorphe à

un tore complexe :
E ' C/Λ, Λ réseau de C.
La loi de groupe sur E coïncide avec celle de C/Λ, et les isogénies deviennent
simplement la multiplication par un nombre complexe : on a une isogénie
[α] : C/Λ → C/Λ0 dès que α ∈ C∗ vérifie αΛ ⊂ Λ0 . Par exemple, le noyau
de la multiplication scalaire [m] est alors E[m](C) = m 1
Λ/Λ, un groupe
isomorphe à (Z/mZ) . 2

Les endomorphismes de E sont alors les α ∈ C tels que αΛ ⊂ Λ. Souvent,

seuls les éléments de Z conviennent, mais pour certains réseaux, des endo-
morphismes supplémentaires apparaissent. L’anneau End(E) est dans ce cas
un Z-module de dimension 2 (en fait, un ordre O dans un corps quadratique
imaginaire) ; on dit que E a multiplication complexe par O.
Les références souvent données pour l’étude des courbes elliptiques sont
[15, 16] ; voir aussi [13] pour un traitement plus moderne.

2 Calcul d’isogénies
2.1. Un peu d’histoire. « Calculer » une isogénie φ : E → E 0 peut avoir
plusieurs significations. Dans ce document, on s’intéresse à deux situations :

• On connaît E et Ker φ, et l’on souhaite calculer une équation de E 0

ainsi que des fractions rationnelles définissant φ (en somme, on sou-
haite construire un quotient explicitement).

• On connaît E, E 0 et éventuellement le degré de φ, et l’on souhaite

retrouver le noyau de φ et des fractions rationnelles la définissant. On
demande donc de calculer entièrement une isogénie lorsque l’on sait
qu’elle existe.
1. Ce n’est pas tout à fait exact : il existe des exceptions lorsque q est un carré et
E est une courbe elliptique supersingulière. Son anneau d’endomorphismes est cependant
toujours plus grand que Z.

3
 La première question est résolue à l’aide des formules de Vélu, proposées
en 1971 [19]. De nombreuses méthodes ont vu le jour pour calculer le noyau
d’une isogénie, en commençant par la méthode de Stark [17], publiée en 1972
et qui concerne les endomorphismes d’une courbe elliptique à multiplication
complexe.
L’histoire récente commence avec les travaux d’Elkies dans les années
1990 : il s’inspire des travaux de Stark et Vélu pour calculer les fractions
rationnelles d’une isogénie, à condition qu’elle soit normalisée. Il fait cir-
culer un manuscrit en 1991–92 (« Explicit isogenies ») puis en publie une
version étendue en 1998 [5]. Dans le même temps, des techniques sont déve-
loppées par Atkin, sous la forme de mails principalement : on peut trouver
certains manuscrits à l’adresse http://www.lix.polytechnique.fr/Labo/
Francois.Morain/. Ces méthodes ont fait l’objet d’articles au journal de
théorie des nombres de Bordeaux [14, 12].
Il n’existe alors pas d’algorithme fonctionnant en petite caractéristique.
En 1994, Couveignes publie sa thèse [2] contenant un algorithme à base de
groupes formels qui résout ce problème. Cet algorithme est complexe, et
cela pousse Lercier à développer en 1996 un algorithme dans le cas de la
caractéristique 2 [10] de complexité non prouvée, mais très intéressant en
pratique. Ce travail est ensuite généralisé par Couveignes [3], qui propose
un algorithme basé sur l’interpolation de l’isogénie en certains points de la
courbe.
Les progrès réalisés depuis prennent surtout la forme d’améliorations et
généralisations de méthodes existantes : Bostan, Morain, Salvy et Schost
améliorent en 2008 la méthode d’Elkies [1], Lercier et Sirvent proposent de
l’utiliser après un relèvement dans les nombres p-adiques pour pouvoir l’uti-
liser en petite caractéristique [11], Lairez et Vaccon [9] précisent la précision
p-adique nécessaire à cette dernière méthode. De Feo, dans sa thèse [6] et
des articles ultérieurs [7] développe la méthode de Couveignes.

Après la présentation des formules de Vélu, on s’intéressera tout d’abord

à la méthode de Stark, pour son intérêt historique et son caractère élémen-
taire, ainsi qu’à la méthode d’Elkies. On présente également la méthode
d’interpolation de Couveignes, qui fournit une solution simple au problème
du calcul d’isogénies en petite caractéristique.

2.2. Les formules de Vélu. Soit E une courbe elliptique donnée sous
forme de Weierstrass
y 2 = x3 + ax + b.
La question posée par Vélu [19] est la suivante : connaissant un sous-groupe
fini G de E(k), comment déterminer une isogénie dont ce sous-groupe est le
noyau ? On supposera Card(G) impair pour simplifier.

4
 Afin de déterminer une équation de la courbe image, on cherche des
fonctions rationnelles x0 , y 0 sur E, G-périodiques et de degrés respectifs 2 et
3 (comme les x, y d’une équation de Weierstrass). On définit ainsi

x0 (P ) = x(P + g) −
X X
x(g),
g∈G g∈G\{0E }

y 0 (P ) = y(P + g)
X

g∈G

pour tout point P ∈ E(k). Pour trouver une équation satisfaite par ces deux
fonctions (c’est-à-dire l’équation de la courbe image), on trouve des fractions
rationnelles f, g telles que x0 = f (x) et y 0 = y g(x) : on regroupe les termes
P + g et P − g, on utilise la loi de groupe et on trouve

3x2 (g) + a x3 (g) + ax(g) + b

" #
x0 = x + +2
X
,
g∈G\{0E }
x − x(g) (x − x(g))2
(1)
3x2 (g) + a x3 (g) + ax(g) + b
" #
0
y =y−y + 4
X
.
g∈G\{0E }
(x − x(g))2 (x − x(g))3

On développe ces expressions en puissances négatives de x et on en déduit

l’équation
y 02 = x03 + a0 x0 + b0
avec
a0 = a − 5 (3x2 (g) + a)
X

g∈G\{0E }
(2)
0
b =b−7 (5x3 (g) + 3ax(g) + 2b).
X

g∈G\{0E }

Le terme constant de x a été ajusté pour trouver une équation réduite. On a

ainsi l’équation de la courbe image, et les expressions (1) donnent l’isogénie
sous forme de fractions rationnelles. Les relations (2) sont souvent exprimées
en fonction des coefficients du polynôme dont les x(g) sont les racines.

2.3. La méthode de Stark. Stark [17] s’intéresse au calcul d’endomor-

phismes d’une courbe elliptique E à multiplication complexe par O, définie
par exemple sur une extension finie de Q et donnée par une équation de la
forme
y 2 = x3 − ax − b.
On a vu qu’il existe un réseau Λ de C tel que E(C) ' C/Λ. Ce paramétrage
est donné par
℘0 (z)
 
z 7→ ℘(z),
2

5
pour z ∈ C/Λ, où ℘ est la fameuse fonction de Weierstrass associée à Λ. Si
β ∈ O, on a un endomorphisme [β]E de E qui s’écrit z 7→ βz dans le point
de vue du tore complexe.
La question est alors d’exprimer cet endomorphisme du point de vue
« algébrique » plutôt qu’analytique, c’est à dire en tant qu’application ra-
tionnelle sur la courbe E. Cela revient à trouver une fraction rationnelle f
telle que l’on ait l’égalité de fonctions méromorphes sur C :

℘(βz) = f (℘(z)).

La fraction f donne alors la coordonnée x de l’endomorphisme [β]E . En

regardant les zéros et pôles de ces séries de Laurent, on peut savoir que f
s’écrit pq , où les polynômes p et q sont de degrés respectifs |β|2 et |β|2 − 1.
La quantité |β|2 est le degré de cet endomorphisme.
Pour calculer ces deux polynômes, Stark utilise un algorithme de dé-
composition en fraction continue inspiré des nombres réels. Lorsque l’on se
donne α ∈ Q, on définit α0 = α et pour tout j ≥ 0,
1
aj = bαj c , αj+1 =
αj − aj

et l’on s’arrête lorsque αj = aj . Le rationnel α est alors égal à

pj 1
= a0 + .
qj 1
a1 +
..
. 1
+
aj

Le principe est exactement le même ici, et cela permet d’écrire facilement

℘(βz) sous forme de fraction rationnelle en ℘(z).
Bien sûr, on manipule dans cet algorithme uniquement un nombre fini
de coefficients des séries de Laurent comme ℘(z). On connaît le degré des
polynômes p, q obtenus à la fin de l’algorithme, ce qui permet de contrôler
le nombre de coefficients nécessaire au calcul. Ces coefficients sont obtenus
à l’aide de l’équation différentielle ℘02 = 4℘3 + 4a℘ + 4b :
1 a b
℘(z) = + z2 + z4 + · · ·
z2 5 7
Telle qu’exposée ci-dessus, la méthode de Stark ne s’applique qu’à des
endomorphismes et non à une isogénie générale.

2.4. La méthode d’Elkies. Les calculs proposés par Elkies [5] partent
de l’idée d’« inverser » les formules de Vélu. Soit φ : E → E 0 une isogénie
de degré `, avec ` = 2n + 1 impair (on conserve cette simplification ici).

6
On se donne une équation de Weierstrass pour E et E 0 ; cette donnée est
équivalente à celles de formes différentielles ωE et ωE 0 . On dit que φ est
normalisée si φ∗ ωE 0 = ωE .
On peut voir que l’isogénie quotient E → E/G donnée par les formules de
Vélu est normalisée. L’idée d’Elkies est alors la suivante : si φ est normalisée,
alors l’équation de Weierstrass de E 0 est celle que l’on aurait obtenue en
appliquant les formules de Vélu à partir de Ker φ. Si le polynôme K(X) =
(−1)n−i σn−i X i a pour racines les abscisses des éléments de Ker φ, les
P

relations de Vélu (2) fournissent le coefficient σ2 ainsi qu’une relation linéaire

entre σ1 et σ3 .
Comment continuer et calculer les coefficients suivants du polynôme ?
Comme φ est normalisée, on peut écrire

N (x)
φ(x, y) = φx (x), yφ0x (x) , φx (x) =


D(x)

où N et D sont des polynômes de degrés ` et ` − 1, et D = K 2 . L’équation

de E 0 donne donc une équation différentielle (notons l’analogie avec les idées
de Stark) :
y 2 φ02 0
x (x) = φx (x) + a φx (x) + b
3 0
(3)
où l’on remplace y 2 par x3 + ax + b et que l’on différencie pour obtenir une
équation du second ordre :

(3x2 + a)φ0x + 2(x3 + ax + b)φ00x = 3φ2x + a0 . (4)

On développe ensuite φx en série de x−1 :

X hi
φx (x) = x + .
i≥1
xi

L’équation différentielle (4) donne une relation de récurrence liant les coef-
ficients hi , qui s’initialise grâce aux relations tirées de (2)

a − a0 b − b0
h1 = , h2 = .
5 7
On peut retrouver les coefficients de K à partir de ceux de φx , puisque l’on
peut réarranger (1) en
0
K 0 (x) K 0 (x)

φx (x) = `x − σ1 − (3x + a)
2
− 2(x3 + ax + b) . (5)
K(x) K(x)

On obtient une relation de récurrence qui permet de déterminer les coef-

ficients de K. Cependant, pour l’utiliser, il faut connaître la quantité σ1
(la somme des racines de K). On peut parfois la déterminer par d’autres
méthodes, mais on ne dispose pas toujours de ce renseignement.

7
 L’algorithme d’Elkies est quadratique en ` en termes d’opérations dans le
corps de base. Tel qu’exposé ci-dessus, il s’applique aux isogénies normalisées
pour lesquelles on dispose d’un renseignement supplémentaire, et n’est donc
pas utilisable directement en général.

Bostan, Morain, Salvy et Schost [1] reprennent cette méthode en 2008 en

proposant deux améliorations. La première est l’utilisation d’une itération
de Newton afin de résoudre l’équation (3) dans les séries formelles ; on passe
ainsi d’un algorithme quadratique en ` à une complexité quasi-optimale,
linéaire en ` à facteurs logarithmiques près. Atteindre cette complexité né-
cessite de plus d’utiliser des algorithmes rapides pour la manipulation des
polynômes et séries formelles, que l’on peut trouver par exemple dans le
livre de von zur Gathen et Gerhardt [8].
La seconde idée est de récupérer le polynôme K(x) non pas à partir de
N (x)
la relation (5), mais directement à partir de la série formelle φx = K(x) 2 à
l’aide d’un algorithme dit de reconstruction rationnelle. Cela nécessite de
calculer un peu plus de coefficients de φx , mais connaître la somme des
racines de K n’est plus nécessaire. En revanche, on demande toujours une
isogénie normalisée.
Remarquons que résoudre les différentes relations de récurrences (ou l’ap-
plication de la méthode de Newton) nécessite de diviser par beaucoup de
petits entiers dans le corps de base. Cet algorithme n’est donc pas utilisable
en petite caractéristique. De plus, on ne sait pas « normaliser » une isogénie
en temps quasi-linéaire : proposer un algorithme quasi-linéaire dans tous les
cas reste une question ouverte.

2.5. L’algorithme de Couveignes. L’algorithme de Couveignes permet

de donner une solution au problème de calcul d’isogénie en petite caracté-
ristique. Soit p un nombre premier, q = pr et E/Fq une courbe elliptique.
L’endomorphisme [p] de E n’est pas séparable : dans la plupart des cas, E
est une courbe dite ordinaire, et l’on a pour tout j ≥ 1

E[pj ](k) ' Z/pj Z.

L’inséparabilité se voit bien : « il n’y a pas assez de points » dans ce noyau

par rapport au degré.
Lorsque φ : E → E 0 est une isogénie de degré ` premier à p, elle définit
une bijection
∼
E[pj ](k) → E 0 [pj ](k).
Pour simplifier, fixons j ≥ 1 et supposons que les points de pj -torsion de
E sont définis sur Fq . C’est alors vrai sur E 0 également, puisque ce sont les
images par φ des points de E. Choisissons deux points P , P 0 qui engendrent
respectivement les groupes cycliques E[pj ](k), E 0 [pj ](k). Il existe alors un
unique a ∈ (Z/pj Z)× tel que φ(P ) = [a]P 0 . Comme φ est un morphisme de

8
groupes, elle envoie également le point [m]P sur [am]P 0 pour tout entier m.
Couveignes propose donc de choisir un coefficient a et de tenter d’interpoler
l’isogénie entre ces points ; si cela échoue, on prend un autre coefficient a
jusqu’à trouver le bon !
Afin d’interpoler une fraction rationnelle de degré `, il faut disposer de
suffisamment de points : il faut choisir l’entier j tel que pj > 4`. Pour
trouver un générateur de E[pj ](Fq ), on calcule un polynôme de division Tj
définissant E[pj ] et on en cherche une racine dans Fq , à l’aide de l’algorithme
de Cantor–Zassenhaus [8].
Bien sûr, en général les points de E[pj ] ne sont pas Fq -rationnels, et
il faut manipuler des extensions du corps Fq . Si Tj se scinde sur Fq en f
facteurs irréductibles de degré d
f
Tj =
Y
Uk,j ,
k=1

il est intéressant de travailler avec les d extensions Fq [X]/Uk,j munies d’iso-

morphismes compatibles, plutôt que dans le gros anneau Fq [X]/Tj . On peut
aussi calculer intelligemment des isomorphismes avec les analogues de ces
corps que l’on obtient avec la courbe E 0 [4]. Afin d’obtenir une meilleure
complexité, il faut également utiliser des méthodes rapides pour la manipu-
lation de polynômes [8] 2 . Lorsque `  p, on obtient un algorithme de coût
essentiellement quadratique en ` en termes de Fq -opérations.
En revanche, le coût est exponentiel en log p, puisqu’il faut manipuler
des polynômes de degré au moins p − 1. Pour cette raison, l’algorithme de
Couveignes n’est pas adapté lorsque log p n’est pas très petit. Pour traiter le
cas de la caractéristique « intermédiaire » (lorsqu’un algorithme de grande
caractéristique comme la méthode d’Elkies n’est pas applicable du fait de
divisions par zéro sans que p soit petit), on peut étendre l’algorithme de
Couveignes en interpolant sur la nk -torsion pour un premier n distinct de `
et p : voir par exemple De Feo, Hugounenq, Plût et Schost [7].

3 Application au comptage de points

Soit p un grand nombre premier et E/Fp une courbe elliptique. On sou-
haite calculer le cardinal du groupe E(Fp ). Cette question est naturelle dans
de nombreux contextes : par exemple, dans l’optique d’utiliser la courbe E
dans un protocole cryptographique, il est souvent important que le cardinal
de E(Fp ) ait un grand facteur premier. Nous allons voir comment utiliser
des isogénies permet d’accélérer ce calcul.
2. On utilise aussi des méthodes spécifiques pour d’autres étapes du calcul, comme
l’interpolation : on renvoie pour cela à [6, 7].

9
 Pour compter les points d’une courbe elliptique en grande caractéristique
en temps polynomial, on utilise l’algorithme de Schoof [14]. On peut montrer

Card E(Fp ) = p + 1 − t,
√
où t est un nombre entier vérifiant |t| ≤ 2 p et tel que le Frobenius πE
vérifie
2
πE − tπE + p = 0.
Comment alors déterminer t ? Si P = (x, y) est un point de E, on doit avoir
2 2
(xp , y p ) − [t](xp , y p ) + [p](x, y) = 0E (6)

On peut donc choisir un point générique P , et tester cette égalité pour toutes
les valeurs permises de t. Vu les bornes de Hasse, cela donne un algorithme
exponentiel en log(p).
Cependant, si P est un point de `-torsion pour un premier `, alors l’éga-
lité (6) restera vraie en remplaçant t par le reste de t modulo `. On peut
ainsi proposer un algorithme multimodulaire : on choisit des premiers `i tels
√
que `i > 4 p (ce qui peut se faire avec `i = O(log p)), puis on calcule t
Q

modulo chaque `i en testant l’égalité (6) comme ci-dessus. On récupère alors

t via les restes chinois. On obtient un algorithme polynomial en log(p), mais
de degré élevé puisque le polynôme de `-division est de degré `2 − 1.

Utiliser des isogénies permet de réduire ce degré : c’est une amélioration

proposée par Elkies à l’algorithme de Schoof. Plus précisément, on peut
montrer que le polynôme X 2 − tX + p est le polynôme caractéristique de πE
vu comme endomorphisme du (Z/`Z)-espace vectoriel E[`](Fp ) de dimension
2. Lorsque ce polynôme est scindé modulo ` (ce qui survient une fois sur 2
environ), il existe des sous-espaces propres pour le Frobenius : ce sont des
sous-groupes rationnels de cardinal `, donc il existe une isogénie rationnelle
de degré ` au départ de E. On dit alors que ` est un nombre premier d’Elkies,
et on procède comme suit :

• On détermine une courbe liée à E par une `-isogénie (à l’aide d’une

équation modulaire, ce dont on ne parlera pas ici) ;

• On détermine son noyau à l’aide de l’algorithme d’Elkies (il faut d’abord

normaliser l’isogénie, ce dont on ne parlera pas non plus) ; on connaît
alors une droite stable par le Frobenius de E[`] ;

• On détermine la valeur propre v` de πE sur cette droite ;

p
• On récupère t = v` + v` mod `, vu le polynôme caractéristique.

Ainsi, on ne manipule plus le polynôme de `-division de degré `2 − 1,

mais seulement un polynôme définissant un sous-groupe de cardinal `, de

10
degré `−1
2 . Il s’agit d’une amélioration importante en pratique. Cependant,
on ne sait pas montrer en général qu’il existe suffisamment de nombres pre-
miers d’Elkies pour pouvoir diminuer la complexité théorique de l’algorithme
de Schoof. D’autres améliorations ont été proposées par Atkin dans le cas
des autres premiers, d’où l’algorithme SEA fréquemment utilisé pour cet
algorithme, implanté entre autres dans PARI [18] et Magma.

Références
[1] A. Bostan, F. Morain, B. Salvy, and É. Schost. Fast algorithms for com-
puting isogenies between elliptic curves. Mathematics of computation,
77(263) :1755–1778, 2008.

[2] J.-M. Couveignes. Quelques calculs en théorie des nombres. PhD thesis,
1994.

[3] J.-M. Couveignes. Computing `-isogenies with the p-torsion. Algorith-

mic Number Theory, ANTS II, L.N.C.S., 1122 :59–65, 1996.

[4] J.-M. Couveignes. Isomorphisms between Artin–Schreier towers. Math.

Comp., 69(232) :1625 – 1631, 2000.

[5] N. D. Elkies. Elliptic and modular curves over finite fields and related
computational issues, 1997. Preprint.

[6] L. De Feo. Fast algorithms for towers of finite fields and isogenies. PhD
thesis, École Polytechnique, 2010.

[7] L. De Feo, C. Hugounenq, J. Plût, and É. Schost. Explicit isogenies in

quadratic time in any characteristic. LMS J. Comp. Math., 19(A) :267–
282, 2016.

[8] J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cam-
bridge University Press, 1999.

[9] P. Lairez and T. Vaccon. On p-adic differential equations with separa-

tion of variables. In Proceedings of the ACM on International Sympo-
sium on Symbolic and Algebraic Computation, ISSAC ’16, pages 319–
323, 2016.

[10] R. Lercier. Computing isogenies in F2n . Algorithmic Number Theory,

ANTS II, L.N.C.S., 1122 :197–212, 1996.

[11] R. Lercier and T. Sirvent. On Elkies subgroups of `-torsion points in

elliptic curves defined over a finite field. Journal de théorie des nombres
de Bordeaux, 20(3) :783–797, 2008.

11
[12] F. Morain. Calcul du nombre de points sur une courbe elliptique dans
un corps fini : aspects algorithmiques. Journal de théorie des nombres
de Bordeaux, 7(1) :255–282, 1995.

[13] J. Nekovár. Algebraic theory of elliptic curves, 2004. Cours de

DEA/M2.

[14] R. Schoof. Counting points on elliptic curves over finite fields. Journal
de théorie des nombres de Bordeaux, 7(1) :219–254, 1995.

[15] J. H. Silverman. The arithmetic of elliptic curves. Springer, 1986.

[16] J. H. Silverman. Advanced topics in the arithmetic of elliptic curves.

Springer, 1994.

[17] H. M. Stark. Class number of complex quadratic fields. In W. Kuyk,

editor, Modular fonctions of one variable I, pages 153–174. Antwerp,
1972.

[18] The PARI Group, Univ. Bordeaux. PARI/GP version 2.9.0, 2017.
available from http://pari.math.u-bordeaux.fr/.

[19] J. Vélu. Isogénies entre courbes elliptiques. Comptes-rendus de l’Aca-

démie des Sciences, Série I, 273 :238–241, 1971.

12