hdr.tex

\documentclass[b5layout]{hdr}

\usepackage[french,english]{babel}
\usepackage{array}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{unicode}
\usepackage[type={CC},modifier={by-nc-sa},imagemodifier={-eu},version={4.0},imagewidth=5em]{doclicense}
\usepackage{fancyhdr}

\usepackage[style=alphabetic,refsegment=chapter,maxnames=20]{biblatex}
\bibliography{isogenies_bib/isogenies,hdr}

\usepackage[pdfusetitle]{hyperref}
\hypersetup{
  unicode=true,
  colorlinks=true,
  citecolor=blue!70!black,
  filecolor=black,
  linkcolor=red!70!black,
  urlcolor=blue,
  pdfstartview={FitH},
  pdfauthor={Luca De Feo},
  pdfsubject={Mathematics},
  pdfkeywords={Cryptography, Number theory, Computer algebra, Elliptic curves, Isogenies, Finite fields},
}

\usepackage{tikz}
\usetikzlibrary{arrows,trees,matrix,decorations,decorations.text,decorations.pathmorphing,calc}
\pgfkeys{/triangle/.code=\tikzset{x={(-0.5cm,-0.866cm)},y={(1cm,0cm)}}}
\pgfkeys{/lattice/.code n args={4}{\tikzset{cm={#1,#2,#3,#4,(0,0)}}}}
\tikzset{
  dotstyle/.style={circle, inner sep = 1.2pt, outer sep = 4pt, fill = gray},
  edgetower/.style={thick},
  edgecomp/.style={thick, lightgray}
}

%% Used by included papers
\usepackage{algorithmic,stmaryrd} % explicit_isogenies
\usepackage[chapter]{algorithm}
\def\algorithmicrequire{\textbf{Input:}}
\def\algorithmicensure{\textbf{Output:}}
\usepackage{bm,mdwlist} % ff_compositum
\usepackage{enumitem,subcaption} % ffisom
\usepackage[ruled, vlined, linesnumbered, algo2e, algochapter]{algorithm2e} % crs

\include{preamble}
\include{hyphenat}

\title{Exploring Isogeny Graphs}
\author{Luca De Feo}

\begin{document}

\frontmatter

\input{covers}

\chapter{Preface}

About ten years removed from my PhD, the time has come to pause and
reflect on my research path. But, even admitting I have come to a
point where I can look back at my work and make sense of it, how to
convey this in a coherent manuscript that still has some value to a
reader?

I don't know if I found the answer, at any rate I could not get a
clear one by asking around. I guess this is part of the exercise. I
chose to write three chapters that survey topics I particularly
endear, in the hope that they motivate readers to get into similar
areas of research. You will judge if I have succeeded.

As a last thing before moving to the main course, I would like to
leave a message in a bottle for future HDR candidates: everyone knows
what an HDR is not, but no one seems to know what it is. You shall
follow the advice of previous candidates, of course, but in the end
you will decide what you make of it, so try and make what is most
valuable to you and your community.

\paragraph{Acknowledgments.} I would like to start by thanking the
person who is responsible for getting me into all of this. He has been
a mentor, a coworker, a friend, a paternal figure, and, above all, he
was the one crazy enough to believe, back in 2007, that isogeny based
cryptography may be a serious thing one day. I am obviously naming
François Morain. Who knows whether isogeny based cryptography would
have been ready on time for NIST's post-quantum competition without
his vision.

The next person, is the one responsible for keeping me from falling
completely into this. She is my best friend, an amazing chef, a
talented artist, a charismatic teacher, and a loving presence. Without
her, I could not have taken the load of stress and fatigue that comes
with preparing this thesis. I am talking of Rachel Deyts.

I want to specially thank my research students: C. Hugounenq,
S. Besnier, L. Brieulle, É. Rousseau, R. Larrieu, J. Kieffer and
M. Veroni. In the end, this manuscript is about them, and the
wonderful moments we have spent working together. I am also grateful
to all my other students for everything they have given to me, but I
can't possibly fit all their names in here.

My coauthors, É. Schost, D. Jao, J. Doliskani, J. Plût, J.-P. Flori,
M. Kohlhase, D. Müller, M. Pfeiffer, N. Thiéry, V. Vasilyev,
T. Wiesing, B. Smith, S. Galbraith, R. Azarderakhsh, B. Koziel,
M. Campagna, B. LaMacchia, C. Costello, P. Longa, M. Naehrig, B. Hess,
J. Renes, A. Jalali, V. Soukharev and D. Urbanik, also deserve a
special thanks.  Research is no fun alone in an office. Even if we are
not technically coauthors, I have spent hours working on things that I
value as much as pure research with E. Bray, J. Demeyer and
V. Delecroix, and I am grateful for that.

A special thank to Louis Goubin, who is the ideal boss, and whose
advice for preparing this manuscript and the defense has been
priceless.

I am honored and humbled that A. Enge, F. Hess and D. Kohel have
accepted to review this manuscript, and that P. Barreto,
J.-M. Couveignes and A. Valibouze have agreed to serve on the jury.
They are among my role models, and it means a lot to me that they have
looked with interest to my work.

I am immensely grateful for the working and leisure time I have spent
with my coworkers at UVSQ, at Inria Saclay, at Télécom Paristech and
at Paris Sud: C. Boura, C. Chaigneau, I. Chilotti, N. Gama, M. Krir, A. Gélin,
A. Mathieu-Mahias, G. Moreno-Socias, J. Patarin, N. Perrin,
M. Quisquater, V. Sécherre, F. Vial-Prado, D. Augot, E. Barelli,
A. Couvreur, V. Ducet, J. Lavauzelle, F. Lévy, B. Meyer, D. Madore,
J. Pieltant, M. Rambaud, H. Randriam, F. Hivert, S. Lelièvre,
B. Pilorget, V. Pons, and I am sure I am forgetting students who have
come and gone.

My life would have been much harder without the invaluable help of our
assistants, C. Le Quéré, I. Moudenner, C. Ducoin, and F. Chevalier.

I want to thank my family for always having been supportive of my life
choices, and for being always ready to come all the way from Italy to
support me in these moments. My friends, for cheering me up and giving
me moments of pleasure away from work.

And finally, thanks to you who are reading this. Your interest in
these pages honors me deeply.

\clearpage
\tableofcontents
\clearpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Introduction}

If you are reading this on a computer screen, chances are that you got
to it by browsing the web. %
You probably went to a search engine, or maybe received a link via
email, or social media. %
You followed the link, landing on some scientific repository, and
downloaded the pdf. %

Two to three hops, each triggering dozens of connections to search
servers, CDNs for static assets, targeted advertisement services, and
trackers of all sorts. %
All over HTTPS. %

In the lapse of a few seconds, your CPU has chosen some standardized
elliptic curves, drawn dozens of random integers, multiplied some
default generators by them, and sent around projective points over the
wire. %
Maybe it is even the year 2050, and, as we have all moved to Siberia
to escape the effects of global warming, your Megacorp branded browser
is now offering perfect forward secrecy through ephemeral
supersingular isogeny key exchange.

Yes. \emph{Supersingular isogeny key exchange}. %
Indeed, this may sound straight out of a William Gibson novel, but it
actually is a real thing. %
And you do not even need to wait for Netherlands to be under water to
use it: Microsoft has released a fork of OpenVPN containing it.%
\footnote{https://github.com/Microsoft/PQCrypto-VPN.} %

The goal of this document is to make those four words sound less
otherworldly, at least for those who have been around asymmetric
cryptography in recent years. %
It is not a course on arithmetic geometry, nor a complete review of
isogeny-based cryptography, not even a monography. %
It is more like a promenade, a stroll around topics related to
\emph{isogeny graphs} that are dearest to my heart. %
A journey through unexplored lands made possible by science and
technological progress. %
Like mathematical \emph{capitaines Nemos} we shall start our journey
on an isolated island, an \emph{elliptic curve} surfacing out of an
uncharted sea. %

We shall start our exploration by diving in the sea. %
We will discover nearby underwater elliptic curves, linked to our
island by \emph{isogenies}. %
We will enter our \emph{Nautilus}, and, equipped with an
\emph{algebraic bathymeter}, we will dive to the sea floor to explore
the slopes of an underwater \emph{volcano}. %

Next, we shall climb to the top of the island to gain a vantage point
and observe the seascape around us. %
We will build observation \emph{towers} to look as far as the remotest
islets, discovering that our tiny island is only a minuscule part of
an immense archipelago: an \emph{isogeny graph} crisscrossed by
isogenies of any \emph{degree}.

Finally, we shall set sail to explore the archipelago, charting the
isogeny routes that link the elliptic curves. %
The theories of \emph{complex multiplication} and of \emph{quaternion
  algebras} will work as a compass, indicating the direction to the
next island. %
However, despite our technological prowess, like seamen in a starless
night, we will miss a fundamental tool: a telemeter to keep track of
the distance between elliptic curves. %
A blessing and a curse, the lack of a telemeter will let us hide
\emph{secrets} in the isogeny graph, confident that any pirate seeking
them will be condemned to wander aimlessly through the archipelago for
centuries to come.

Breaking out of the metaphors, Chapter~\ref{cha:tate} deals with
isogenies of elliptic curves and algorithmic problems related to
them. %
We will introduce the \nameref{prob:expl-isog}, first studied by
Elkies, and present some algorithms to solve it. %
We will then focus on elliptic curves over finite fields, and on a
specific algorithm for the explicit isogeny problem due to
Couveignes. %
To understand it better, we will study the \emph{Frobenius
  endomorphism}, and see how it determines the types of isogenies
around an elliptic curve; by looking at its action on the \emph{Tate
  module}, we will gain a global view on the \emph{isogeny graph}. %
Then, an \emph{effective version of \hyperref[th:tate]{Tate's isogeny
    theorem}} will provide us with an effective way to \emph{probe the
  depths} of the isogeny graph. %
Armed with this tool, we will end the chapter with a generalization of
Couveignes' algorithm, currently the algorithm with the best
complexity for solving the explicit isogeny problem. %

The effective version of Tate's theorem is only as efficient as the
algorithms at our disposal to compute in the algebraic closure of a
finite field. %
In Chapter~\ref{cha:fpbar} we shall study algorithms to represent and
compute with finite extensions of a finite field. %
We will review algorithms to compute irreducible polynomials, then
move to two radically different paradigms to represent the algebraic
closure of finite fields. %
One, based on \emph{special families of irreducible polynomials}, will
extend some algorithms for irreducible polynomials by adding to them
more features: \emph{compatibility}, \emph{incrementality} and
\emph{uniqueness}. %
The other one, based on \emph{lattices of arbitrary irreducible
  polynomials}, will be founded on an algorithm for computing
isomorphisms of finite fields; we shall thus review all known
algorithms for this problem, and see how they are related to
algorithms for irreducible polynomials. %

The goal of this chapter is not only to be a review in computational
complexity, but also to explore the practical implementation aspects
of the algorithms. %
All along the exposition, we will refer to the available
implementations in the most popular computer algebra systems and
libraries (Magma, SageMath, PARI/GP, Nemo, Flint, NTL, \dots), and
highlight the implementation challenges and possible ways forward. %

Finally, in Chapter~\ref{cha:crypto} we will come to the much
anticipated isogeny-based cryptography. %
This novel type of cryptography, pioneered by Couveignes in the
nineties, is built on the algebraic structure of large isogeny
graphs. %
We will see how the theory of \emph{complex multiplication} and that
of \emph{quaternion algebras} determine the structure of these graphs,
and how they prove their \emph{expansion} properties. %
We will then focus, only, on key exchange protocols based on isogenies
graphs; we will review three proposals: Couveignes' original one based
on \emph{ordinary graphs}, a recent twist on it, named CSIDH, based on
\emph{supersingular $\F_p$-graphs}, and another one based on
generic \emph{supersingular graphs} named SIDH. %
We will conclude the chapter by discussing security of isogeny-based
primitives. %
The main selling point for isogeny-based algorithms is their supposed
resistance to quantum attacks, we shall thus review the known quantum
algorithms for breaking them, and discuss the impact on security
parameters. %

The whole document is meant as an introduction to a research area,
thus it purposely ignores some important topics and skips technical
details. %
Each chapter is accompanied by one or two research articles,
previously appeared in peer reviewed journals and proceedings, for the
reader interested in gaining more insights. %
These are, for Chapter~\ref{cha:tate},
\begin{quote}
  Luca De Feo, Cyril Hugounenq, Jérôme Plût and Éric Schost. %
  ``Explicit isogenies in quadratic time in any characteristic''. %
  \emph{LMS Journal of Computation and
    Mathematics}~\cite{defeo2016explicit}.
\end{quote}
Introducing the generalization of Couveignes' algorithm. %
For Chapter~\ref{cha:fpbar},
\begin{quote}
  Luca De Feo, Javad Doliskani and Éric Schost. %
  ``Fast Arithmetic for the Algebraic Closure of Finite Fields''. %
  \emph{Proceedings of the 39th International Symposium on Symbolic
    and Algebraic Computation (ISSAC 2014)}~\cite{DeDoSc2014}.
\end{quote}
On realizing the algebraic closure of a finite field, and
\begin{quote}
  Ludovic Brieulle, Luca De Feo, Javad Doliskani, Jean-Pierre Flori
  and Éric Schost. %
  ``Computing Isomorphisms and Embeddings of Finite Fields''. %
  \emph{Mathematics of Computation}~\cite{brieulle2018computing}.
\end{quote}
On the complexity and the practical performance of isomorphism
algorithms for finite fields. %
For Chapter~\ref{cha:crypto},
\begin{quote}
  Luca De Feo, David Jao and Jérôme Plût. %
  ``Towards Quantum-Resistant Cryptosystems from Supersingular
  Elliptic Curve Isogenies''. %
  \emph{Journal of Mathematical Cryptology}~\cite{defeo+jao+plut12}.
\end{quote}
introducing the key exchange protocol SIDH, and
\begin{quote}
  Luca De Feo, Jean Kieffer and Benjamin Smith. %
  ``Towards practical key exchange from ordinary isogeny graphs''. %
  \emph{Proceedings of AsiaCrypt 2018}~\cite{10.1007/978-3-030-03332-3_14}.
\end{quote}
on improvements to the Couveignes--Rostovtsev--Stolbunov key exchange
protocol. %

Finally, this document also wants to serve as a snapshot of the
current state of the research in the various areas it touches. %
For this reason, each chapter is terminated by a section called
``Perspectives'', pointing to interesting related research topics,
both easy and hard.

I hope that you will appreciate the topics I have selected, enjoy the
flow of the presentation, and forgive me for omissions and
approximations.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mainmatter

\thispagestyle{empty}
\begin{otherlanguage}{french}
  
  \epigraph{\it Vous avez poussé votre œuvre aussi loin que vous le
    permettait la science terrestre. Mais vous ne savez pas tout, vous
    n'avez pas tout vu. Laissez-moi donc vous dire, monsieur le
    professeur, que vous ne regretterez pas le temps passé à mon
    bord. Vous allez voyager dans le pays des
    merveilles. L'étonnement, la stupéfaction seront probablement
    l'état habituel de votre esprit. Vous ne vous blaserez pas
    facilement sur le spectacle incessamment offert à vos yeux.}{---
    Jules Verne,\\Vingt mille lieues sous les mers}

  \epigraph{\it Je voudrais avoir vu ce que nul homme n'a vu encore,
    quand je devrais payer de ma vie cet insatiable besoin
    d'apprendre!  Qu'ai-je découvert jusqu'ici? Rien, ou presque rien,
    puisque nous n'avons encore parcourur que six mille lieues à
    travers le Pacifique!}{--- Jules Verne,\\Vingt mille lieues sous
    les mers}

  \epigraph{\it Pour moi l'étude est un secours, une diversion
    puissante, un entraînement, une passion qui peut me faire tout
    oublier. Comme vous, je suis homme à vivre ignoré, obscur, dans le
    fragile espoir de léguer un jour à l'avenir le résultar de mes
    travaux, au moyen d'un appareil hypothétique confié au hasard des
    flots et des vents.}{--- Jules Verne,\\Vingt mille lieues sous
    les mers}
\end{otherlanguage}

\chapart{art/20000leagues-color}
\chapter{Bathymetry}
\label{cha:tate}

\epigraph{\it Ce fut Tasman qui découvrit ce groupe en 1643, l'année
  où Torricelli inventait le baromètre, et où Louis XIV montait sur le
  trône. Je laisse à penser lequel de ces faits fut le plus utile à
  l'humanité.}{--- Jules Verne,\\Vingt mille lieues sous les mers}

\noindent What is an isogeny, anyway? %
Despite the imposing sounding name, an isogeny is a pretty simple
concept: a morphism between two elliptic curves, preserving their
algebraic structure (both as a group and as a variety). %

Isogenies of abelian varieties have been studied since the beginning
of the 19th century, by the likes of Abel, Jacobi, Weierstrass,
Riemann, Picard, etc. %
According to Wikipedia%
\footnote{See \url{https://en.wikipedia.org/wiki/Isogeny}. No source
  is given, though.}, %
the name ``isogeny'' was introduced in the 20th century by André Weil,
to avoid confusion with ``isomorphism''. %
After the \emph{schematic} revolution in algebraic geometry, major
contributions to the theory of abelian varieties and isogenies were
made by Cartier, Serre, Tate, and, obviously, Grothendieck. %
With the development of computer algebra, people grew increasingly
interested in effective methods, with important contributions being
made by Schoof, Atkin, Elkies, Satoh, Kedlaya, and many others. %
In recent years, isogenies have found various applications in
cryptology, sparking a remarkable wave of results on their algorithmic
properties. %

In this chapter, we shall take the algorithmic point of view, and
discuss algorithms to compute and classify isogenies of elliptic
curves. %
The focal point of interest will be the \emph{Frobenius endomorphism}
of an elliptic curve defined over a finite field. %
We will first learn how it governs the properties of isogenies ``in
the neighborhood'' of an elliptic curve. %
We will then define \emph{isogeny graphs}---graphs whose vertices are
elliptic curves and whose edges are isogenies---, and, not unlike a
biologist, set on a mission to classify them. %
Isogeny graphs inherit from an \emph{infinite tree} structure, but
over a finite field they must ``fold'' in order to fit into a finite
space. %
Thanks to a celebrated theorem of Tate, we will discover that the
Frobenius endomorphism, much like the DNA of a living creature,
determines the ``folding'' of the isogeny graph. %

Even knowing the structure of an isogeny graph, it is not always easy
to navigate it. %
An \emph{effective version} of Tate's theorem will provide us with a
tool to ``probe the depth'' of a curve inside an isogeny graph. %
Armed with our brand new tool, we will conclude the chapter by
presenting the algorithm with the best known complexity to compute an
isogeny between two given elliptic curves. %


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Isogenies}

An isogeny is a non-constant algebraic map between elliptic curves,
preserving the point at infinity. %
An isogeny is also a surjective group morphism of elliptic curves. %
It turns out these definitions are equivalent, but, before getting
these pages drenched in more properties and theorems, let's have a
look at an example.

The map $ϕ$ from the elliptic curve $y^2=x^3+x$ to $y^2=x^3-4x$
defined by
\begin{equation}
  \label{eq:isog-example}
  \begin{aligned}
    ϕ(x,y) &= \left(\frac{x^2+1}{x},y\frac{x^2-1}{x^2}\right),\\
    ϕ(0,0) &= ϕ(\O) = \O
  \end{aligned}
\end{equation}
is an isogeny. %
As an algebraic map it has degree $2$, which implies that it is a
two-to-one map, as it can be inferred from the polynomial degrees. %


\begin{figure}
  \centering
  \begin{tikzpicture}[x=0.03\textwidth,y=0.03\textwidth]
    \begin{scope}
      \node[anchor=center] at (0,7) {$E \;:\; y^2 = x^3 + x$};

      \draw[thin,gray] (0,-6) -- (0,6);
      \draw[thin,gray] (-6,0) -- (6,0);

      \foreach \x/\y in {0/0,5/3,-4/3,-3/5,-2/1,-1/3} {
        \draw[blue,fill] (\x,\y) circle (0.2) node(E_\x_\y){}
        (\x,-\y) circle (0.2) node(E_\x_-\y){};
      }
    \end{scope}

    \draw[black!10!white,thick] (8,-7) -- +(0,14);
    
    \begin{scope}[shift={(16,0)}]
      \node at (0,7) {$E' \;:\; y^2 = x^3 - 4x$};

      \draw[thin,gray] (0,-6) -- (0,6);
      \draw[thin,gray] (-6,0) -- (6,0);

      \foreach \x/\y in {0/0,2/0,3/2,4/2,6/4,-2/0,-1/5} {
        \draw[color=blue,fill] (\x,\y) circle (0.2) node(F_\x_\y){}
        (\x,-\y) circle (0.2) node(F_\x_-\y){};
      }
    \end{scope}

    \begin{scope}[color=red,-latex,dashed]
        \path
        (E_5_3) edge (F_3_2)
        (E_-4_3) edge (F_4_-2)
        (E_-3_5) edge (F_4_2)
        (E_-2_1) edge (F_3_-2)
        (E_-1_3) edge (F_-2_0);
        \path
        (E_5_-3) edge (F_3_-2)
        (E_-4_-3) edge (F_4_2)
        (E_-3_-5) edge (F_4_-2)
        (E_-2_-1) edge (F_3_2)
        (E_-1_-3) edge (F_-2_0);
    \end{scope}
  \end{tikzpicture}
  \caption{The isogeny $(x,y) \mapsto \bigl((x^2+1)/x,\;y(x^2-1)/x^2\bigr)$,
    as a map between curves defined over $\F_{11}$.}
  \label{fig:isog-example}
\end{figure}


What does an isogeny ``look like''? %
Drawing the above one in $\R^2$ would look rather messy, but an
isogeny defined over the rationals is still an isogeny if we reduce
modulo a prime $p$. %
Figure~\ref{fig:isog-example} plots the action of the
isogeny~\eqref{eq:isog-example} on the image of the curves in
$\F_{11}$. %
A red arrow indicates that a point of the left curve is sent onto a
point on the right curve; the action on the point in $(0,0)$, going to
the point at infinity, is not shown. %
We observe a symmetry with respect to the $x$-axis, a consequence of
the fact that $ϕ$ is a group morphism; and, by looking closer, we may
also notice that collinear points are sent to collinear points, also a
necessity for a group morphism. %

Something strikes us, though: the map looks by no means surjective! %
This is because, when we think of isogenies, we think of them as
geometric objects, acting on the extension of the curves to the
algebraic closure. %
This is not dissimilar from the way power-by-$n$ maps act on the
multiplicative group $k^×$ of a field $k$: the map $x↦x^2$, for
example, is a two-to-one (algebraic) group morphism on
$\F_{11}^\times$, and those elements that have no preimage, the
non-squares, will have exactly two square roots in $\F_{11^2}$, and so
on. %
In much the same way, in an algebraic closure $\bar{\F}_{11}$ of
$\F_{11}$, the isogeny $ϕ$ becomes surjective and every point gains
exactly two antecedents. %
This analogy is more profound that it may seem, and shall bear its
fruits in Chapter~\ref{cha:fpbar}.

For elliptic curves defined over a field of characteristic $p>0$,
there is another kind of isogeny. %
Let $E:y^2=x^3+ax+b$ be an elliptic curve, let $q$ be a power of $p$, and let
$E^{(q)}:y^2=x^3+a^qx+b^q$. %
The isogeny $π_q:E→ E^{(q)}$ defined by
\begin{equation}
  \begin{aligned}
    π_q(x,y) &= (x^q,y^q),\\
    π_q(\O) &= \O
  \end{aligned}
\end{equation}
is a \emph{purely inseparable} isogeny of degree $q$. %
We call $π_q$ a \emph{Frobenius isogeny}. %
Despite being of degree $q$, Frobenius isogenies have trivial kernel,
and are one-to-one over finite fields (and other perfect fields). %

% Plotting the action of $π_p$ on the curve of
% Figure~\ref{fig:isog-example} would not be very telling, since in this
% case $E^{(p)}=E$ and the map acts like the identity on $\F_{11}$. %
% However $π_p$ is an important map, called the \emph{Frobenius
%   endomorphism} of $E$, and often denoted simply by $π$. %
% It permutes the points of $E/\bar{\F}_{11}$ in a non trivial way,
% reflecting the action of the Galois group of $\bar{\F}_{11}/\F_{11}$
% on $E$. %

Any isogeny can be decomposed as a product of a Frobenius isogeny and
a \emph{separable} isogeny:
\begin{equation*}
  \begin{tikzpicture}
    \node(E) at (0,0) {$E$};
    \node(Ep) at (2,0) {$E^{(q)}$};
    \node(E') at (4,0) {$E'$};
    \draw[->,auto] (E) edge node{\small $π_q$} (Ep)
    (Ep) edge node{\small $ϕ_s$} (E')
    (E) edge[bend right=20] node[below]{\small $ϕ$} (E');
  \end{tikzpicture}
\end{equation*}
Computing this decomposition is also easy given rational functions for
$ϕ$: simply factor out the powers of $p$ from the polynomials. %
For these reasons we shall be mostly concerned with separable
isogenies and their computations.

The most unique property of separable isogenies is that they are 
entirely determined by their kernel. %

\begin{proposition}
  Let $E$ be an elliptic curve defined over an algebraically closed
  field, and let $G$ be a finite subgroup of $E$. %
  There is a curve $E'$, and a separable isogeny $ϕ$, such that
  $\ker ϕ=G$ and $ϕ:E→ E'$. %
  Furthermore, $E'$ and $ϕ$ are unique up to composition with an
  isomorphism $E'≃E''$. %
\end{proposition}

Said otherwise, for any finite subgroup $G⊂E$, we have an exact
sequence of algebraic groups
\begin{equation*}
  0 → G → E \overset{ϕ}{→} E' → 0.
\end{equation*}
Uniqueness up to isomorphisms justifies the notation $E/G$ for the
isomorphism class of the image curve $E'$. %
Now, it would be useful if we could find a way to define a canonical
representative inside $E/G$. %
It turns out there is a pretty natural way to define one.

\begin{definition}[Normalized isogeny]
  Let $E,E'$ be two elliptic curves, $ω_E,ω_E'$ their \emph{invariant
    differential}, $ϕ:E→ E'$ a separable isogeny and
  $ϕ^*:Ω_{E'}→ Ω_E$ its \emph{pullback}. %
  We say that $ϕ$ is \emph{normalized} if its pullback preserves the
  invariant differentials, i.e., $ϕ^*(ω_{E'})=ω_E$. %
\end{definition}

Since $ϕ$ is separable, $ϕ^*$ is an isomorphism of vector spaces of
dimension 1. %
Said otherwise, if $ϕ$ is not normalized, then it is only ``off'' by a
(non-zero) constant $ϕ^*(ω_{E'})=cω_E$, and we can easily normalize
$ϕ$ by a change of variables. %
This also shows that, for fixed $E$ and $\ker ϕ$, the normalized
isogeny is unique, and justifies abusing the notation $E/G$ to mean
the image of the normalized isogeny with kernel $G$.\footnote{Note
  that this convention is not universal in the literature, as there
  are other useful choices for a canonical representative of $E/G$.}

Conversely, since any non-constant morphism of elliptic curves
necessarily has finite kernel, we have a canonical bijection between
the finite subgroups of a curve $E$ and the normalized isogenies with
domain $E$. %
This correspondence is rich in consequences: it is an easy exercise to
prove the following useful facts. %

\begin{corollary}\ 
  \begin{enumerate}
  \item Any isogeny of elliptic curves can be decomposed as a product
    of prime degree isogenies.
  \item Let $E$ be defined over an algebraically closed field $k$, let
    $ℓ$ be a prime different from the characteristic of $k$, then
    there are exactly $ℓ+1$ normalized isogenies of degree $ℓ$ with
    domain $E$.
  \end{enumerate}
\end{corollary}

Slightly more work is required to prove the following,
fundamental, theorem (the difficulty comes essentially from the
inseparable part, see~\cite[III.6.1]{Sil} for a
detailed proof).

\begin{theorem}[Dual isogeny theorem]
  Let $ϕ:E→ E'$ be an isogeny of degree $m$. %
  There is a unique isogeny $\hat{ϕ}:E'→ E$ such that
  \[\hat{ϕ}∘ϕ = [m]_E, \quad ϕ∘\hat{ϕ} = [m]_{E'}.\] %
  $\hat{ϕ}$ is called the \emph{dual isogeny of $ϕ$}; it has the
  following properties:
  
  \begin{enumerate}
  \item $\hat{ϕ}$ has degree $m$;
  \item $\hat{ϕ}$ is defined over $k$ if and only if $ϕ$ is;
  \item $\widehat{ψ∘ϕ} = \hat{ϕ}∘\hat{ψ}$ for any isogeny $ψ:E'→ E''$;
  \item $\widehat{ψ+ϕ} = \hat{ψ} + \hat{ϕ}$ for any isogeny $ψ:E→ E'$;
  \item $\deg ϕ = \deg\hat{ϕ}$;
  \item $\hat{\hat{ϕ}} = ϕ$.
  \end{enumerate}
\end{theorem}

Note that, since $[m]^*(ω)=mω$, if $ϕ$ is normalized so that
$ϕ^*ω'=ω$, $\hat{ϕ}$ almost never is. %
The computational counterpart to the kernel-isogeny correspondence is
given by Vélu's much celebrated formulas. %

\begin{proposition}[{Vélu~\cite{velu71}}]
  \label{th:velu}
  Let $E:y^2=x^3+ax+b$ be an elliptic curve defined over a field $k$,
  and let $G⊂E(\bar{k})$ be a finite subgroup. %
  The normalized separable isogeny $ϕ:E→ E/G$, of kernel $G$, can be
  written as
  \begin{equation*}
    ϕ(P) = \left(
      x(P) + \sum_{Q∈G\setminus\{\O\}}x(P+Q)-x(Q),\\
      y(P) + \sum_{Q∈G\setminus\{\O\}}y(P+Q)-y(Q)
    \right);
  \end{equation*} %
  and the curve $E/G$ has equation $y^2=x^3+a'x+b'$, where
  \begin{align*}
    a' &= a - 5\sum_{Q∈G\setminus\{\O\}}(3x(Q)^2+a),\\
    b' &= b - 7\sum_{Q∈G\setminus\{\O\}}(5x(Q)^3+3ax(Q)+2b).
  \end{align*}
\end{proposition}

But how ``good'' are Vélu's formulas from a computational
perspective? %
``Pretty good'', is the message we want to convey, but, in order to
understand the question, we need to discuss \emph{rationality}. %
Let $E$ be defined over a field $k$ with algebraic closure
$\bar{k}$. %
We say that an isogeny $ϕ:E→ E'$ is \emph{defined over $k$}, or
\emph{$k$-rational}, if $ϕ$ is invariant under the action of the
Galois group of $\bar{k}/k$. %
This is equivalent to $ϕ$ being defined by rational maps with
coefficients in $k$, and implies\footnote{The converse is only true up
  to \emph{twist}.} that $\ker ϕ$ is stable under $\Gal(\bar{k}/k)$. %
It implies that $E'$ is defined over $k$, but the converse is not
true. %

In the rest of this work, when we say ``an isogeny'', we really mean
``an isogeny defined over the base field'', unless specified
otherwise. %
What are the input and output sizes of Vélu's formulas, if we
restrict to $k$-rational isogenies? %

The output is a pair of rational fractions, and, letting $ℓ=\#G$, it
is not too difficult to see that they have $O(ℓ)$ coefficients. %
The input is the kernel $G$, and, since it is finite, it must be
generated by at most two elements. %
However $G$ is only stable under $\Gal(\bar{k}/k)$, implying that its
elements are defined in an (abelian) extension of degree in
$O(ℓ)$. %
Thus, in general, $G$ is represented by $O(\ell)$ coefficients of $k$. %

Now, if we apply mindlessly Vélu's formulas, we need at least $O(ℓ^2)$
coefficients in $k$ to write down all the elements of $G$. %
A better approach is to represent $G$ by a polynomial with
coefficients in $k$ that vanishes on all $P∈G$, for example
\begin{equation*}
  h_G(x) = \prod_{P∈G\setminus\{\O\}} (x - x(P)).
\end{equation*}
The polynomial $h_G$ is called the \emph{kernel
  polynomial}\footnote{Other works prefer defining the kernel
  polynomial as the square root of $h_G$, however this adds some
  complications when $\#G$ is even.} of $G$, and has coefficients in
$k$ if and only if $ϕ$ is $k$-rational; it can be computed from the
generators of $G$ in only $\tildO(ℓ)$ operations over $k$. %
Following Kohel~\cite{kohel}, we can rewrite Vélu's formulas in terms
of $h_G$, then, their evaluation can also be accomplished in
$\tildO(ℓ)$ operations.

In conclusion, we see that Vélu's formulas make the kernel/isogeny
correspondence explicit, using a quasi-optimal number of operations in
general. %
This will be crucial when we will study isogeny-based cryptosystems in
Chapter~\ref{cha:crypto}, however, we will encounter there some
examples where the cost of evaluating an isogeny is exponentially
lower than that of Vélu's formulas. %


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The explicit isogeny and other problems}

When it comes to computations, Vélu's formulas are only part of the
story: how do we find a rational kernel $G$ in the first place?
Elkies, while working on point counting~\cite{elkies92,elkies98},
famously baptized this the \emph{explicit isogeny problem}.

\begin{problem}[Explicit isogeny problem]
  \label{prob:expl-isog}
  Let $E$ be an elliptic curve, and let $ℓ$ be an integer. %
  Find, if it exists, an isogeny of degree $ℓ$ with domain $E$.
\end{problem}

A slightly modified version of the same problem is often found in the
literature.

\begin{problem}
  \label{prob:expl-isog-2}
  Let $E$ and $E'$ be two elliptic curves, and $ℓ$ an integer. %
  Decide whether there exists an isogeny $ϕ:E→ E'$ of degree $ℓ$,
  and compute its kernel.
\end{problem}

The many variants of the explicit isogeny problem have kept the
research community busy for more than twenty years, and still do
today. %
Let's have a closer look at it. %

\paragraph{Elkies' algorithm.}
For a start, it should be noticed that both variants are by no means
``hard''. %
Indeed, we have explicit formulas for adding points on a curve $E$,
from which we can deduce an explicit formula for multiplying points on
$E$ by any scalar $ℓ∈ℤ$. %
Said otherwise, we have an explicit formula for the
multiplication-by-$ℓ$ isogeny, and, by reading its denominators, we
can deduce its kernel polynomial $h_ℓ$.\footnote{Up to a constant,
  $h_ℓ$ is the square of $ψ_ℓ$, the \emph{$ℓ$-th division polynomial}.
  See~\cite[III.4]{blake+seroussi+smart} for explicit formulas.} %

Let us assume for simplicity that $ℓ$ is prime and different from the
characteristic, then we know there are at most $ℓ+1$ normalized
isogenies of degree $ℓ$ from $E$. %
Factoring $h_ℓ$ over the field of definition $k$ of $E$ lets us
compute all possible kernel polynomials of order $ℓ$, and thus all
possible isogenies. %
At most $ℓ+1$ applications of Vélu's formula will then give the answer
to either of the two variants of the explicit isogeny problem. %
Since $E[ℓ]≃(ℤ/ℓℤ)^2$ over the algebraic closure, $h_ℓ$ has degree
$ℓ^2-1$, thus this algorithm costs no more than factoring a degree
$O(ℓ^2)$ polynomial in $k[x]$. %

We see that the matter is not solving the explicit isogeny
problem. The matter is solving it fast!

An interesting case, and the one Elkies was originally interested in,
is when the curves are defined over a finite field. %
Let us relax the problem a bit, and see what can be told about it. %
Decisional versions, first: two elliptic curves are said to be
\emph{isogenous} if there exists an isogeny connecting them (this is
an equivalence relation, thanks to the dual isogeny theorem).

\begin{problem}
  \label{prob:isogenous}
  Let $E,E'$ be two elliptic curves defined over a finite field
  $\F_q$, decide whether they are isogenous.
\end{problem}

Tate~\cite[Th.~1(c)]{Tate} famously showed\footnote{Tate, citing
  Mumford, also points out that, for the case of elliptic curves, this
  is an easy consequence of the much celebrated work of
  Deuring~\cite{deuring41}.} that $E$ and $E'$ are isogenous over
$\F_q$ if and only if $\#E(\F_q)=\#E'(\F_q)$. %
Schoof's point counting algorithm~\cite{schoof85,schoof95} completely
settles the problem by computing the orders of $E$ and $E'$ in
polynomial time in $\log q$. %
However, when we add a degree constraint on the isogeny, the problem immediately
becomes harder, even for finite fields. %

\begin{problem}
  \label{prob:ell-isogenous}
  Let $E,E'$ be two elliptic curves, and $ℓ$ be an integer. Decide
  whether they are $ℓ$-isogenous.
\end{problem}

The \emph{modular polynomial} helps solve this problem. %
Assuming $ℓ$ is prime, the $ℓ$-th modular polynomial, denoted by
$Φ_ℓ(x,y)$, is a bivariate polynomial with coefficients in $ℤ$,
symmetric in $x$ and $y$, of degree $ℓ+1$ in each variable, with the
following property: two elliptic curves $E,E'$ are $ℓ$-isogenous if
and only if $Φ_ℓ(j(E),j(E'))=Φ_ℓ(j(E'),j(E))=0$. %
We stress that the definition of $Φ_ℓ$ is independent of the base
field. %
Given that $Φ_ℓ$ has $O(ℓ^2)$ coefficients (and rather large ones),
using it to decide the explicit isogeny problem is asymptotically only
slightly better than factoring the division polynomial; it is however
usually considerably more efficient in practice, especially when
tables of modular polynomials are precomputed, as is the case in
computer algebra systems such as Pari~\cite{Pari}, Magma~\cite{MAGMA},
or SageMath~\cite{Sage}. %

The modular polynomial can also be used to produce all isogenous
elliptic curves, up to isomorphism, to a given curve: simply plug
$j(E)$ in $Φ_ℓ$, then factor $Φ_ℓ(j(E),y)$ to find the isogenous
$j$-invariants. %
Elkies used this approach to reduce the explicit isogeny problem to
Problem~\ref{prob:expl-isog-2}, but he managed to extract even more
information from $Φ_ℓ$: he showed how to obtain a \emph{normalized
  equation} for the image curve.

\begin{theorem}[{\cite{elkies92,schoof95,elkies98}}]
  Let $E:y^2=x^3+ax+b$ be an elliptic curve, let $j$ be its
  $j$-invariant and let $j'$ be such that $Φ_ℓ(j,j')=0$. %
  Assume that $(∂Φ_ℓ/∂y)(j,j')≠0$, and define
  \begin{equation}
    \label{eq:elkies-modpol}
    \begin{aligned}
      λ &= \frac{-18}{ℓ}\frac{b}{a}\frac{\frac{∂Φ_ℓ}{∂x}(j,j')}{\frac{∂Φ_ℓ}{∂y}(j,j')}j,\\
      a' &= -\frac{1}{48}\frac{λ^2}{j'(j'-1728)}\frac{1}{ℓ^4},\\
      b' &= -\frac{1}{864}\frac{λ^3}{(j')^2(j'-1728)}\frac{1}{ℓ^6}.
    \end{aligned}
  \end{equation}
  Then there is a normalized isogeny of degree $ℓ$ from $E$ to
  $E':y^2=x^3+a'x+b'$.
\end{theorem}

Elkies' theorem prompts us to define a weaker variant of the explicit
isogeny problem.

\begin{problem}[Inverse Vélu problem\footnote{The name is ours and
    not attested in the literature.}]
  Let $E,E'$ be elliptic curves such that there exists a normalized
  isogeny $ϕ:E→ E'$ of degree $ℓ$. %
  Compute the kernel of $ϕ$.
\end{problem}

Unsurprisingly, Elkies also gave the solution to this problem
in~\cite{elkies92,elkies98}. %
He observed that the rational fractions defining $ϕ$ are related by a
differential equation, involving only the coefficients of $E$ and
$E'$. %
Solving the differential equation gives the rational fractions, and
thus the kernel. %
This gives a method to solve the inverse Vélu problem in $O(ℓ^2)$
operations over the base field, or even $\tildO(ℓ)$ using computer
algebra techniques as suggested by Bostan, Morain, Salvy and
Schost~\cite{bostan+morain+salvy+schost08}. %

We have, essentially, sketched the computation involved in the
Schoof-Elkies-Atkin (SEA) point counting algorithm~\cite{schoof95},
for those that are called \emph{Elkies primes} (more on these
later). %
However, the last part of Elkies' algorithm, the solution to the
inverse Vélu problem, only works when the characteristic is $0$ or
\emph{large enough}. %
While this is good enough for counting points of elliptic curves
defined over a prime field $\F_p$, it fails, for example, over binary
fields. %

\paragraph{Couveignes' algorithm.}
After Elkies, others set out to solve the explicit isogeny problem in
small characteristic. %
While Elkies' method is grounded in complex analysis, and thus
naturally works in characteristic $0$,
Couveignes~\cite{couveignes94,couveignes96} and
Lercier~\cite{lercier96} introduced ``more algebraic'' methods, that
only work over finite fields. %

The one that shall interest us here is Couveignes' second method: a
strikingly simple idea to solve Problem~\ref{prob:expl-isog-2}
directly. %
It is based on the observation that any isogeny $ϕ:E→ E'$ must
preserve Sylow subgroups:
\begin{equation}
  ϕ(E[r^k]) \subseteq E'[r^k] \quad\text{for any prime $r$ and $k≥0$},
\end{equation}
with equality if $r$ does not divide $\deg ϕ$. %
If $E/\F_{p^n}$ is an ordinary curve, $E[p^k]≃ℤ/p^kℤ$ has a
particularly simple structure. %
The idea is to compute $E[p^k]$ and $E'[p^k]$ for $k$ large enough
(precisely, $p^k\sim 4\deg ϕ$), make a guess for the exact image of
one group into the other, and \emph{interpolate} the isogeny. %
If the guess was right, the computed isogeny can be verified through
Vélu's formulas; if not a new guess is made. %
Given that the $p^k$-torsion groups are cyclic, at most $φ(p^k)$
different guesses must be made. %

Despite its simplicity, Couveignes' algorithm requires some heavy
computer algebra artillery to achieve a decent complexity, but with
some effort it can be made to run in $\tildO(ℓ^2p^3)$
operations~\cite{couveignes00,df+schost09,df10}. %
However, the polynomial dependency in $p$ is a serious handicap,
quickly making the algorithm unusable as the characteristic grows. %
Couveignes' other algorithm is affected by the same problem, whereas
Lercier's algorithm only works when $p=2$.

With the introduction of $p$-adic alternatives to Schoof's point
counting
algorithm~\cite{satoh00,kedlaya01,kedlaya04,lauder04,10.2307/24522768},
interest in solutions to the explicit isogeny problem limited to such
small characteristic started to fade. %
Later, Lercier and Sirvent~\cite{lercier+sirvent08} explained how to
extend Elkies' algorithm to finite fields of any characteristic by
lifting the explicit isogeny problem to a $p$-adic field. %
Their algorithm only has a logarithmic dependency in the
characteristic, and gracefully degrades to Elkies' algorithm when $p$
becomes large enough. %
Said otherwise, Lercier and Sirvent effectively rendered all previous
algorithms obsolete! %

Incidentally, this coincides with the beginning of my career in
research, one that started off by desperately trying to beat the
cycles out of an algorithm that would be made obsolete before the end of
my first year as a PhD student.%
\footnote{I can only imagine FM's cold sweats
  when Lercier and Sirvent published their algorithm. I did not
  understand at the time. I do now.}

Nevertheless, Couveignes' algorithm is still a great source of
inspiration, with many ramifications that we shall explore in the rest
of this work. %
By the end of this chapter it will be clear that its algebraic nature,
deeply related to Tate's isogeny theorem, has more to offer than what
may appear at first glance. %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The neighborhood}

From now on, $\F_q$ will be a finite field of characteristic $p$, and
all elliptic curves and isogenies will be defined over it, unless
stated otherwise. %

We want to explore the ``neighborhood'' of $E/\F_q$, i.e., given a
prime $ℓ$, how many $ℓ$-isogenous curves to $E$ are there? What
properties do they have?

Fortunately, we have a Swiss-army-knife to answer these questions. %
The \emph{Frobenius endomorphism} is the map
\begin{equation*}
  \begin{aligned}
    π : E &→ E,\\
    (x,y) &↦ (x^q,y^q).
  \end{aligned}
\end{equation*}
Hasse's well known theorem states that $π$, as an element of the
endomorphism ring $\End(E)$, satisfies a quadratic equation with
integer coefficients $π^2 + q = tπ$, where $t$ is called the
\emph{trace} of $π$. %
Hasse also proved that $Δ_π=t^2-4q≤0$, with equality happening only if
$E$ is supersingular. %
$Δ_π$ is called the \emph{discriminant of $π$}. %

An isogeny $ϕ:E→E/G$ is $\F_q$-rational if and only if $π(G)=G$, which
suggests looking at the restriction of $π$ to $E[ℓ]$. %
Assume $ℓ≠p$, then $E[ℓ]$ is a group of rank $2$ and $π$ acts on it
like an element of $\GL_2(\F_ℓ)$, up to conjugation. %
Clearly, the order of $π$ in $\GL_2(\F_ℓ)$ is the degree of the
smallest extension of $\F_q$ where all $ℓ$-isogenies of $E$ are
defined. %
But we can tell even more by diagonalizing the matrix: $π$ must have
between $0$ and $2$ eigenvalues, and the corresponding eigenvectors
define kernels of rational isogenies. %
We thus are in one of the following four cases\footnote{In the point
  counting literature, Case~(0) is known as the \emph{Atkin case}, and
  Case~(2) as the \emph{Elkies case}.}:
\begin{itemize}
\item[(0)] $π$ is not diagonalizable in $\F_ℓ$, then $E$ has no
  $ℓ$-isogenies.
\item[(1.1)] $π$ has one eigenvalue of (geometric) multiplicity one,
  i.e., it is conjugate to a non-diagonal matrix
  $\mat{λ&*\\0&λ}$; then
  $E$ has one $ℓ$-isogeny.
\item[(1.2)] $π$ has one eigenvalue of multiplicity two, i.e., it acts
  like a scalar matrix
  $\mat{λ&0\\0&λ}$; then
  $E$ has $ℓ+1$ isogenies of degree $ℓ$.
\item[(2)] $π$ has two distinct eigenvalues, i.e., it is conjugate to
  a diagonal matrix
  $\mat{λ&0\\0&μ}$ with
  $\lambda\neq\mu$; then $E$ has two $\ell$-isogenies.
\end{itemize}

Naturally, the number of eigenvalues of $π$ depends on the
factorization of the polynomial $x^2-tx+q$ over $\F_ℓ$, or
equivalently on whether ${Δ_π}$ is a square modulo $ℓ$. %

Each of the four cases also corresponds to a different factorization
pattern of the modular polynomial. %
The following proposition is at the heart of Atkin's improvement to
Schoof's point counting algorithm. %

\begin{proposition}[Atkin~\cite{atkin91,atkin92}]
  Let $E/\F_q$ be a curve with $j(E)≠0,1728$. %
  Let $ℓ$ be a prime different from the characteristic, and let $Φ_ℓ$
  be the $ℓ$-th modular polynomial. %
  The number of distinct $\F_q$-rational normalized $ℓ$-isogenies of
  $E$ is equal to the number of linear factors of $Φ_ℓ(j(E),y)$ over
  $\F_q$; furthermore, the factorization degree pattern of
  $Φ_ℓ(j(E),y)$ falls into one of these four categories:
  \begin{itemize}
  \item[(0)] $r,\dots,r$ for some $r$ dividing $ℓ+1$;
  \item[(1.1)] $1,ℓ$;
  \item[(1.2)] $1,\dots,1$;
  \item[(2)] $1,1,r,\dots,r$ for some $r$ dividing $ℓ-1$.
  \end{itemize}
\end{proposition}

For ordinary elliptic curves, Kohel~\cite{kohel} showed that this
classification can be further refined by introducing a notion of
``depth'' of an elliptic curve. %
Let $K=ℚ(π)$ be an imaginary quadratic number field where we identify
the Frobenius $π$ to one root of $x^2-tx+q$. %
Let $\O_K$ be the ring of integers of $K$ then $\End(E)$ is isomorphic
to an order $\O$
\[ℤ[π] \subseteq \O \subseteq \O_K.\] %
We have already seen that two elliptic curves are isogenous over
$\F_q$ if and only if they have the same number of points;
equivalently, they are isogenous if and only if $ℚ(π_E)≃ℚ(π_{E'})$. %
Kohel refined Tate's theorem as follows.

\begin{proposition}[{Kohel~\cite[Prop.~21]{kohel}}]
  Let $E,E'$ be elliptic curves defined over a finite field, and let
  $\O,\O'$ be their respective endomorphism ring. %
  Suppose that there exists an isogeny $ϕ:E→E'$ of prime degree $ℓ$,
  then $\O$ contains $\O'$ or $\O'$ contains $\O$, and the index of
  one in the other divides $ℓ$.
\end{proposition}

For a fixed prime $ℓ$, Kohel defines a curve $E$ to be \emph{at the
  surface} if $v_ℓ([\O_K:\End(E)])=0$, where $v_ℓ$ is the $ℓ$-adic
valuation. %
$E$ is said to be \emph{at depth $d$} if $v_ℓ([\O_K:\End(E)])=d$; the
maximal depth being $d_{\max}=v_ℓ([\O_K:ℤ[π]])$, curves at depth
$d_{\max}$ are said to be \emph{at the floor (of rationality)}, and
$d_{\max}$ is called the \emph{height} of the graph of $E$. %
Kohel calls then an $ℓ$-isogeny \emph{horizontal} if it goes to a
curve at the same depth, \emph{descending} if it goes to a curve at
greater depth, \emph{ascending} if it goes to a curve at lesser
depth. %

But how many horizontal and vertical $ℓ$-isogenies does a given curve
have? %
Typically this question is answered by the theory of complex
multiplication, but we shall use another strategy that better serves
our purpose. %
So far, the Frobenius endomorphism has only given us a ``local'' view
on the neighboring curves. %
We need to ``elevate'' our point of view and look further away, in
order to gain a global view on the whole isogeny class. %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{How isogeny graphs fold}

An \emph{isogeny graph} is a connected graph whose vertices are
elliptic curves up to isomorphism, and whose edges are isogenies under
some restrictions. %
In this chapter we are only interested in graphs of $ℓ$-isogenies, for
some fixed prime $ℓ$; other types of isogeny graphs will appear in
Chapter~\ref{cha:crypto}. %
Because of the dual isogeny theorem, these isogeny graphs are
undirected; technically we should be more properly speaking of
directed multi-graphs, since multiple edges and self-loops are
possible, but these cases are rare enough that we can deal with them
explicitly. %

As a first example, let us start with elliptic curves over the complex
numbers. %
We know every such curve has exactly $ℓ+1$ isogenies, thus every vertex in the isogeny
graph has out degree $ℓ+1$. %
If we let $E/ℂ$ be a curve \emph{without complex multiplication},
i.e., such that $\End(E)=ℤ$, then its connected component cannot have
loops, otherwise that would provide a non-trivial endomorphism of
$E$. %
Hence, the isogeny graph of $E$ is an infinite $(ℓ+1)$-tree, as
pictured in Figure~\ref{fig:infinite-tree}. %

\begin{figure}
  \centering
    \begin{tikzpicture}[scale=0.6]
      \def\levels{6}
      \draw[fill] (0:0) circle (2pt);
      \foreach \i in {1,...,\levels} {
        \pgfmathparse{3*2^\i}
        \let\nodes\pgfmathresult
        \foreach \j in {1,3,...,\nodes} {
          \pgfmathparse{\j + (-1)^div(\j,2)}
          \let\lower\pgfmathresult
          \ifthenelse{\i = \levels}{
            \draw[dotted] (360/\nodes*\j : \i) --
            (360/\nodes*\lower : \i - 1);
          }{
            \draw[fill] (360/\nodes*\j : \i) circle (2pt) --
            (360/\nodes*\lower : \i - 1);
          }
        }
      }
    \end{tikzpicture}
  
    \caption{Infinite $2$-isogeny graph of elliptic curves without
      complex multiplication.}
  \label{fig:infinite-tree}
\end{figure}

To study the structure of these graphs we introduce a tool, a sort of
``lighthouse'' planted at the origin, lighting the graph as it extends
away towards infinity. %
Here is an intuition: if we put $E$ at the origin of the graph,%
\footnote{An infinite tree has no well defined origin, but we may
  arbitrarily choose one.} %
its neighbors are determined by the cyclic subgroups of $E[ℓ]$; if we
``climb'' to $E[ℓ^n]$, we will be able to ``see'' as far as the ball
of radius $n$ around $E$. %
To make sense of the whole graph, it thus feels natural to climb
``infinitely high'', i.e., to ascend to the \emph{Tate module}
$T_ℓ(E)$. %

The \emph{Tate module} $T_ℓ(E)$ is the \emph{projective limit}
\begin{equation*}
  T_ℓ(E) = \varprojlim E[ℓ^n]
\end{equation*}
given by the natural projections
\begin{equation*}
  E[ℓ^n]\overset{[ℓ]}{→}E[ℓ^{n-1}].  
\end{equation*}
Since the $E[ℓ^n]$ are $ℤ/ℓ^nℤ$-modules, $T_ℓ(E)$ has a $ℤ_ℓ$-module
structure, where $ℤ_ℓ$ denotes the $ℓ$-adic integers. %
Any isogeny $ϕ:E→E'$ induces a morphism $ϕ_ℓ:T_ℓ(E)→T_ℓ(E')$ on the
Tate modules, and we may prove that \emph{no information is lost} in
the process (see \cite[III,~Th~7.4]{Sil}). %

\begin{theorem}
  \label{th:pre-tate}
  Let $E,E'$ be elliptic curves defined over a field $k$, and let $ℓ$
  be a prime different from the characteristic of $k$. %
  The canonical map %
  \begin{equation*}
    \Hom(E,E')⊗ℤ_ℓ → \Hom(T_ℓ(E),T_ℓ(E'))
  \end{equation*}
  is injective.
\end{theorem}

We can thus associate elements of $\GL_2(ℚ_ℓ)$ to the isogeny graph
rooted in $E$ as follows. %
Fix a basis of $T_ℓ(E)$, there are $ℓ+1$ isogenies of degree $ℓ$ from
$E$ to other curves $E'$, determined by their respective kernels; up
to a change of basis of $T_ℓ(E')$ the matrix $ϕ_ℓ$ (acting on the
left) associated to $ϕ:E→E'$ is one of
\begin{equation}
  \label{eq:serre-elem}
  \begin{pmatrix}
    ℓ&0\\0&1
  \end{pmatrix},\quad
  \begin{pmatrix}
    1&a\\0&ℓ
\end{pmatrix}
  \text { for $0≤a<ℓ$}.
\end{equation}
By composing these elementary matrices, we obtain the matrix of any
isogeny of degree $ℓ^n$; then, quotienting by the center of
$\GL_2(ℚ_ℓ)$, we factor out endomorphisms of $E$.

We thus define an infinite tree on $\PGL_2(ℚ_ℓ)/\PGL_2(ℤ_ℓ)$,
isomorphic to the graph of $E$, by associating the identity matrix to
the origin, and the matrices $ϕ_ℓ$ to the paths $ϕ:E→E'$, as shown in
Figure~\ref{fig:serre-tree}. %
The \emph{tree of $\PGL_2(ℚ_ℓ)$} was already studied by
Serre~\cite[II]{SL2},%
\footnote{Note that Serre uses a different convention for the
  elementary matrices in Eq.~\eqref{eq:serre-elem}: he has them act on
  the right, instead of on the left, and thus obtains
  $\mat{1&0\\0&ℓ}, \mat{ℓ&a\\0&1}, \dots$ as a basis.} %
and is at the heart of various constructions of \emph{expander
  graphs}~\cite{LubPS,Lub,cryptoeprint:2018:593}, a topic that we
shall encounter again in Chapter~\ref{cha:crypto}.%
\footnote{I am grateful to J. Plût for explaining this to me, and for
  providing the Ti\emph{k}Z code for Figure~\ref{fig:serre-tree}} %

\begin{figure}
  \centering
  \begin{tikzpicture}[grow cyclic,level distance=8ex]
    \tikzstyle{level 1}=[sibling angle=120]
    \tikzstyle{level 2}=[sibling angle=90]
    \tikzstyle{level 3}=[sibling angle=70]
    \node{$\mat{1&0\\0&1}$}
    child{ node{$\mat{1&0\\0&2}$}
      child { node {$\mat{1&0\\0&4}$}
        child { node {$\mat{1&0\\0&8}$} }
        child { node {$\mat{1&4\\0&8}$} }
      }
      child { node {$\mat{1&2\\0&4}$}
        child { node {$\mat{1&2\\0&8}$} }
        child { node {$\mat{1&6\\0&8}$} }
      }
    }
    child{ node{$\mat{1&1\\0&2}$}
      child { node {$\mat{1&1\\0&4}$}
        child { node {$\mat{1&1\\0&8}$} }
        child { node {$\mat{1&5\\0&8}$} }
      }
      child { node {$\mat{1&3\\0&4}$}
        child { node {$\mat{1&3\\0&8}$} }
        child { node {$\mat{1&7\\0&8}$} }
      }
    }
    child{ node{$\mat{2&0\\0&1}$}
      child { node {$\mat{2&1\\0&2}$}
        child { node {$\mat{2&3\\0&4}$} }
        child { node {$\mat{2&1\\0&4}$} }
      }
      child { node {$\mat{4&0\\0&1}$}
        child { node {$\mat{4&1\\0&2}$} }
        child { node {$\mat{8&0\\0&1}$} }
      }
    }
    ;
  \end{tikzpicture}
  \caption{Dyadic Serre tree, representing isogenies of degree $2^n$
    on $T_2(E)$.}
  \label{fig:serre-tree}
\end{figure}

Despite the nice drawings, these graphs are, algebraically,
``boring'': the choice of an origin is arbitrary, and they look the
same from every vertex. %
Things get more interesting if we go back to finite fields. %
Any curve $E/\F_q$ can be seen as the reduction modulo $p$ of some
curve $E/\bar{ℚ}$; thus it must inherit the connectivity structure of
the isogeny graph of $E/\bar{ℚ}$. %
However, there is only a finite number of curves defined over $\F_q$,
and not all isogenies will be $\F_q$-rational. %
Thus, the infinite tree of $\PGL_2(ℚ_ℓ)$ must somehow ``fold'' to fit
inside $\F_q$. %

For example, if $E/\F_q$ is a supersingular curve, we shall see in
Chapter~\ref{cha:crypto} that its isogeny graph ``folds'' to a finite
$(ℓ+1)$-regular graph containing all supersingular curves, up to
$\bar{\F}_q$-isomorphisms. 

For the case of ordinary curves, we have already discussed the notion
of ``depth'', we thus know that, as we travel along a path of
descending isogenies, there is an algebraic invariant that tells us
how far we are from the surface. %
Said otherwise, unlike the graph of $E/ℂ$ without complex
multiplication, that of $E/\F_q$ has one (or more) recognizable
origins. %

Is it possible to read on $T_ℓ(E)$ the depth of $E$? %
We again turn to the Frobenius endomorphism $π$ for help. %
Tate's isogeny theorem makes a stronger statement than
Theorem~\ref{th:pre-tate}, by restricting to morphisms that are
invariant under the action of $π$: it tells us that, for finite
fields, studying Galois-invariant morphisms of $T_ℓ(E)$ is the same as
studying rational isogenies of $E$.

\begin{theorem}[{Tate~\cite{Tate}}]
  \label{th:tate}
  Let $\F_q$ be a finite field of characteristic $p$, and let $ℓ≠p$ be
  a prime. %
  Let $E,E'$ be elliptic curves defined over $\F_q$, the canonical
  map %
  \begin{equation*}
    \Hom_{\F_q}(E,E')⊗ℤ_ℓ → \Hom_{\Gal(\bar{\F}_q/\F_q)}(T_ℓ(E),T_ℓ(E'))
  \end{equation*}
  is an isomorphism of $ℤ_ℓ$-modules.
\end{theorem}

Tate's theorem has many important consequences. %
Among those, we have already mentioned that $E$ and $E'$ are isogenous
if and only if $\#E(\F_q)=\#E'(\F_q)$. %
Furthermore, the action of $π$ on $T_ℓ(E)$ provides a $2$-dimensional
representation of $\Gal(\bar{\F}_q/\F_q)$, and Tate's theorem states
that $E$ and $E'$ are isogenous over $\F_q$ if and only if $T_ℓ(E)$
and $T_ℓ(E')$ are isomorphic as $ℚ_ℓ$-representations. %
By explicitly computing this representation we obtain an
\emph{effective version of Tate's theorem}; one that lets us, in
Kohel's words, ``probe the depths''. %

We again let $K=ℚ(π)$ be an imaginary quadratic number field where we
identify the Frobenius $π$ to one root of $x^2-tx+q$; we let
$Δ_π=t^2-4q$ be the \emph{discriminant} of $ℤ[π]$, and $Δ_K$ the
\emph{fundamental discriminant} of $\O_K$. %
In particular, $[\O_K:ℤ[π]]=\sqrt{Δ_π/Δ_K}$. %

\begin{proposition}[{Miret \emph{et al.}~\cite{MIRET200867},
    Hugounenq~\cite{hugounenq:tel-01635463}}]
  \label{th:tate-matrix-gen}
  Let~$E/\F_q$ be an ordinary elliptic curve with Frobenius
  endomorphism~$π$, and let $h=v_ℓ(\sqrt{Δ_π/Δ_K})$. %
  There exists a unique $e ∈ \{0,h\}$ such that $π|T_ℓ(E)$~is
  conjugate, over~$ℤ_ℓ$, to a matrix $M=\mat{a&ℓ^e\\c&d}$ with
  $ad∧ℓ=1$, $a=d\pmod{ℓ^h}$, and $v_ℓ(Δ_π) ≤ v_ℓ(c) + e$. %
  In particular, $M=\mat{a&ℓ^e\\0&a}\pmod{ℓ^h}$. %
  
  Moreover, $h=v_ℓ([\O_K:ℤ[π]])$ is the height of the graph of $E$;
  if~$E$ lies at the surface, then $e=h$, otherwise $h - e$~is the
  depth of~$E$.
\end{proposition}

In the case where $π^2-tπ+q$ splits in $ℤ_ℓ$, i.e., when
$\leg{Δ_K}{ℓ}=1$, we have a more precise statement.

\begin{proposition}[{D., Hugounenq, Plût, Schost~\cite{defeo2016explicit}}]
  \label{th:tate-matrix-elkies}
  Let~$E/\F_q$ be an ordinary elliptic curve with Frobenius
  endomorphism~$π$. %
  Assume that the characteristic polynomial of~$π$ has two distinct
  roots~$λ, μ$ in~$ℤ_ℓ$, and let $h=v_ℓ(λ-μ)=v_ℓ(\sqrt{Δ_π/Δ_K})$. %
  Then there exists a unique $e ∈ \{0,h\}$ such that $π|T_ℓ(E)$~is
  conjugate, over~$ℤ_ℓ$, to the matrix $\mat{λ&ℓ^e\\0&μ}$. %
\end{proposition}

We thus have an effective \emph{bathymeter} to navigate the isogeny
graph: it is indeed sufficient to compute $π|T_ℓ(E)$ up to precision
$ℓ^h$, i.e., $π|E[ℓ^h]$, in order to determine the depth of $E$. %
This generalizes previous partial results of Miret \emph{et
  al.}~\cite{MiretMSTV06,MIRET200867} and Ionica and
Joux~\cite{ionica+joux13}. %

But what about horizontal isogenies? %
Can we construct indefinitely long walks entirely made of them? %
The effective version of Tate's theorem also gives us an effective way
to characterize horizontal isogenies. %
Indeed, if $ϕ:E→E'$ is an $\F_q$-rational isogeny, $ϕ_ℓ$ its
restriction to $T_ℓ(E)$, and we let $π,π'$ be the Frobenius
endomorphisms of $E,E'$, then $π' = ϕ_ℓπϕ_ℓ^{-1}$ (where we have
tensored by $ℚ_ℓ$ to make sense of $ϕ_ℓ^{-1}$). %

We have already conveniently arranged all isogenies of degree $ℓ^n$ in
the graph of Figure~\ref{fig:serre-tree}, thus, if we are given a
matrix for $π|T_ℓ(E)$, all we have to do to compute $π|T_ℓ(E')$ is to
conjugate by the corresponding matrix $ϕ_ℓ$. %
For example, assume that the characteristic polynomial of $π$ has two
distinct roots, so that we are in the setting of
Proposition~\ref{th:tate-matrix-elkies}. %
If $π$ diagonalizes as $\mat{λ&0\\0&μ}$, the two isogenies
$\mat{1&0\\0&ℓ}$ and $\mat{ℓ&0\\0&1}$ do not change the matrix of $π$,
thus they are both horizontal, whereas all other isogenies are
descending. %
On the other hand, if $π$ can only be put in the form
$\mat{λ&ℓ^e\\0&μ}$ with $e<h$, we see that the isogeny $\mat{ℓ&0\\0&1}$ is
ascending, whereas all others are descending. %
Finally, if $π$ is of the form $\mat{λ&1\\0&μ}$, then we have one
ascending isogeny as before, however no descending isogeny can be
rational. %

By applying the same reasoning to $\leg{Δ_K}{ℓ}=-1,0$, we can prove a
complete classification of rational isogenies. %
This is summarized in Table~\ref{tab:periodic-table}. %

\begin{theorem}[{Kohel~\cite{kohel}}]
  \label{prop:isogeny-count}
  Let~$E/\F_q$ be an ordinary elliptic curve, $π$ its Frobenius
  endomorphism, and $Δ_K$ the fundamental discriminant of $ℚ(π)$. %
  \begin{enumerate}
  \item If $E$ is not at the floor, there are $ℓ+1$ isogenies of
    degree $ℓ$ from~$E$, in total.
  \item If $E$ is at the floor, there are no descending $ℓ$-isogenies
    from~$E$.
  \item If $E$ is at the surface, then there are
    $\left(\frac{Δ_K}{ℓ}\right)+1$~horizontal $ℓ$-isogenies from~$E$
    (and no ascending $ℓ$-isogenies).
  \item If $E$ is not at the surface, there are no horizontal
    $ℓ$-isogenies from~$E$, and one ascending $ℓ$-isogeny.
  \end{enumerate}
\end{theorem}

\begin{table}
  \centering
  \def\arraystretch{1.3}
  \begin{tabular}{c | c | c | c c c}
    \multicolumn{3}{c|}{} & \multicolumn{3}{c}{Isogeny types}\\
    \multicolumn{3}{c|}{} & $→$ & $↑$ & $↓$\\
    \hline
    $v_ℓ(Δ_π/Δ_K)=0$ & $ℓ\nmid[\O_K:\O]]$ & $ℓ\nmid[\O:ℤ[π]]$ & $1+\leg{Δ_K}{ℓ}$& &\\
    \hline
    & $ℓ\nmid[\O_K:\O]]$ & $ℓ\mid[\O:ℤ[π]]$ &$1+\leg{Δ_K}{ℓ}$& &$ℓ-\leg{Δ_K}{ℓ}$\\
    $v_ℓ(Δ_π/Δ_K)>1$ & $ℓ\mid[\O_K:\O]]$ & $ℓ\mid[\O:ℤ[π]]$ &  &$1$&$ℓ$\\
    & $ℓ\mid[\O_K:\O]]$ & $ℓ\nmid[\O:ℤ[π]]$ & &$1$& 
  \end{tabular}
  \caption{Number and types of $ℓ$-isogenies, according to splitting
    type of the characteristic polynomial of $π$.}
  \label{tab:periodic-table}
\end{table}

This theorem shows that, away from the surface, isogeny graphs just
look like $ℓ$-regular complete trees of bounded height, with $ℓ$
descending isogenies at every level except the floor. %
However, the surface has a more varied structure:
\begin{itemize}
\item[(0)] If $\leg{Δ_K}{ℓ}=-1$, there are no horizontal isogenies:
  the isogeny graph is just a complete tree of degree $ℓ+1$ (in the
  graph theoretic sense) at each level but the last. %
  We call this the \emph{Atkin case}, as it is an extension of the
  Atkin case in the SEA point counting algorithm.
\item[(1)] If $\leg{Δ_K}{ℓ}=0$, there is exactly one horizontal
  isogeny $ϕ:E→E'$ at the surface. %
  Since $E'$ also has one horizontal isogeny, it necessarily is
  $\hat{ϕ}$, so the surface only contains two elliptic curves, each
  the root of a complete tree. %
  We call this the \emph{ramified case}.
\item[(2)] The case $\leg{Δ_K}{ℓ}=1$ is arguably the most interesting
  one. %
  Each curve at the surface has exactly two horizontal isogenies, thus
  the subgraph made by curves on the surface is two-regular and
  finite, i.e., a cycle. %
  The eigenvalue $λ$ (resp. $μ$) of $π$ defines an eigenspace, that
  projects onto a cyclic subgroup of $E[ℓ^n]$, which is the kernel of
  an $ℓ^n$-isogeny represented by the matrix $\mat{ℓ^n&0\\0&1}$
  (resp. $\mat{1&0\\0&ℓ^n}$). %
  Hence, $λ$ and $μ$ define two opposite \emph{directions} on the
  cycle, independent of the starting point, and dual to one another. %

  Below each curve of the surface there are $ℓ-1$ curves, each the
  root of a complete tree. %
  We call this the \emph{Elkies case}, again by extension of point
  counting. %
\end{itemize}

\begin{figure}[h]
  \centering
  \begin{tikzpicture}
    \begin{scope}
      \draw[fill] (0,0) circle (2pt)
      -- (-1,-1) circle (2pt)
      (0,0) -- (0,-1) circle (2pt)
      (0,0) -- (1,-1) circle (2pt);
      \node at (0,-2) {Atkin: $\left(\frac{Δ_K}{ℓ}\right) = -1$};
    \end{scope}    

    \begin{scope}[xshift=3.5cm]
      \draw[fill] (0,0) circle (2pt)
      -- (-0.5,-1) circle (2pt)
      (0,0) -- (0.5,-1) circle (2pt)
      (0,0) -- (2,0) circle (2pt)
      -- (1.5,-1) circle (2pt)
      (2,0) -- (2.5,-1) circle (2pt);
      \node at (1,-2) {ramified: $\left(\frac{Δ_K}{ℓ}\right) = 0$};
    \end{scope}
    
    \begin{scope}[xshift=9cm]
      \draw[fill] (-0.8,0) node[coordinate] (A) {} circle (2pt)
      -- +(0,-1) circle (2pt)
      (0,-0.3) node[coordinate] (B) {} circle (2pt)
      -- +(0,-1) circle (2pt)
      (0.8,0) node[coordinate] (C) {} circle (2pt)
      -- +(0,-1) circle (2pt);
      \draw[bend right=20]
      (A) edge (B)
      (B) edge (C)
      (C) edge[dashed,bend right=90] (A);
      \node at (0,-2) {Elkies: $\left(\frac{Δ_K}{ℓ}\right) = +1$};
    \end{scope}
  \end{tikzpicture}
  \caption{The three shapes of volcanoes of $2$-isogenies of height 1.}
  \label{fig:volcanology}
\end{figure}

The three cases are summarized in Figure~\ref{fig:volcanology}. %
Tate's theorem only allows us to tell as much; to know more on the
number and sizes of isogeny graphs, we shall need the theory of
\emph{complex multiplication}, however we delay this to
Chapter~\ref{cha:crypto}, where it will be used to construct
``cryptographic'' isogeny graphs. %

The shapes of the graphs, in particular the Elkies case, suggest a
geological metaphor: Fouquet and Morain~\cite{fouquet+morain02}
famously called them \emph{isogeny volcanoes}. %
Adhering to this metaphor, from now on we shall call \emph{crater} the
cycle at the surface of an Elkies volcano, but we shall refrain from
using this name for the surface of other types of volcanoes.%
\footnote{The literature, including my own
  works~\cite{defeo2016explicit}, is inconsistent on the use of the
  word ``crater'' for non-Elkies volcanoes.} %
Of course, to reconcile Kohel's maritime metaphors with Fouquet and
Morain's, we shall assume that isogeny volcanoes are underwater, with
the crater just touching the sea surface.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Explicit isogenies in quadratic time}

Armed with our new knowledge on isogeny volcanoes, we can now come
back to the explicit isogeny problem. %

Recall Couveignes' algorithm: it \emph{interpolates} an isogeny
$ϕ:E→E'$ of degree $r$ over the $p^k$-torsion subgroups, for $k$ large
enough. %
Its main disadvantage is the polynomial dependency in $p$, the
characteristic of the base field; in practice, Couveignes' algorithm
is hardly practical for $p>3$. %

To get rid of the bad dependency in $p$, the obvious idea is to
replace $E[p^k]$ with $E[ℓ^k]$ for some small prime $ℓ$ coprime to
$r$, say $ℓ=2$. %
However, a naive algorithm based on this would have a much worse
complexity than Couveignes' original algorithm. %
Indeed $E[p^k]$ is cyclic, thus there are only $φ(p^k)$ possible
morphisms $E[p^k]→E'[p^k]$ to test; if each test takes $p^{k+O(1)}$
operations, the whole algorithm takes $p^{2k+O(1)}=r^2p^{O(1)}$. %
On the other hand, $E[ℓ^k]$ is of rank $2$, thus
$\Hom(E[ℓ^k],E'[ℓ^k])$ is isomorphic to $\GL_2(ℤ/ℓ^kℤ)$ and has size
$O(ℓ^{4k})$; if each interpolation test takes $ℓ^{2k+O(1)}$
operations, the whole algorithm takes $ℓ^{6k+O(1)}=r^3ℓ^{O(1)}$. %

But we are not interested in \emph{any} isogeny: we are explicitly
looking for a \emph{rational} isogeny, thus we can use all that we
have learned so far. %
Indeed, we are just applying Tate's theorem: trying to identify, among
all matrices in $\Hom(T_ℓ(E),T_ℓ(E'))$ (truncated to precision $ℓ^k$),
the one that corresponds to the isogeny $ϕ$. %
Since $ℓ$ does not divide $\deg ϕ$, the curves $E$ and $E'$ have the
same depth in their respective volcanoes (which may or may not be
distinct); and since $ϕ$ is rational, its matrix must commute with
$π$. %
Thus, even though $\Hom(T_ℓ(E),T_ℓ(E'))$ has dimension $4$ as a
$ℤ_ℓ$-module, we can focus on the, potentially smaller, submodule of
matrices that leave $π$ stable. %

Concretely, assume that the characteristic polynomial of $π$ has two
distinct roots, and suppose that $E$ is on the crater. %
Then we can find bases for $E[ℓ^k]$ and $E'[ℓ^k]$ such that the
respective Frobenius endomorphisms act like $\mat{λ&0\\0&μ}$ on
each. %
Since $ϕ$ is rational, it must map the eigenspace of $λ$ in $E[ℓ^k]$
into the eigenspace of $λ$ in $E'[ℓ^k]$, and similarly for $μ$. %
Said otherwise, $ϕ$ must be represented by a diagonal matrix, thus the
search space is reduced to a dimension $2$ submodule, that is
$O(ℓ^{2k})$ different possibilities to try, for an overall complexity
of only $r^2ℓ^{O(1)}$ operations. %

What we just described is the gist of the algorithm presented in
``Explicit isogenies in quadratic time in any characteristic'' written
with C.~Hugounenq, J.~Plût and É.~Schost~\cite{defeo2016explicit}, and included
in the appendix to this document. %
Although I must admit that the title cheats in two ways:
\begin{itemize}
\item The algorithm solves Problem~\ref{prob:expl-isog-2} in quadratic
  time, i.e., not exactly the ``explicit isogeny problem'' as we have
  stated it, and thus does not improve the complexity of the SEA point
  counting algorithm;
\item The algorithm only achieves quadratic complexity for
  \emph{almost all} prime powers $q$ and \emph{almost all} pairs of
  isogenous curves $E,E'$ defined over $\F_q$. %
\end{itemize}

In our defense, artificial as Problem~\ref{prob:expl-isog-2} may seem,
ours is the only algorithm that achieves quadratic complexity in the
isogeny degree, beating even Lercier and Sirvent's algorithm. %
Although its impact is purely theoretical, the techniques employed are
of independent interest and may find useful applications in other
contexts. %

Concerning the second problem, the difficulty comes from the fact that
our techniques only work when the characteristic polynomial of $π$
splits over $ℤ_ℓ$, i.e., when $ℓ$ is an Elkies prime for $E$. %
However, it may happen that no small prime is Elkies for $E$, and
indeed curves such that none of the first $O(\log q)$ primes is Elkies
do exist, although they are ``rare''.%
\footnote{Interestingly, we will look at the opposite problem in
  Chapter~\ref{cha:crypto}: construct curves such that a lot of small
  primes are Elkies.} %

Before we close this chapter, let us summarize the steps of our
``ℓ-adic Couveignes' algorithm''. %
Note that, to run the algorithm, we need an Elkies prime $ℓ$ for $E$. %
It would be easy to find one if we knew the order of $E(\F_q)$, but this
would be cheating, since one of the goals of Couveignes' algorithm is
to help count the points of $E$. %
Instead we show that the number of roots of $π$ in $ℤ_ℓ$ can be
``discovered'' as we proceed in the steps below. %
For simplicity, we are also going to assume that $E$ and $E'$ are on
the craters of the respective volcanoes; note that we can always
reduce to this situation using
Proposition~\ref{th:tate-matrix-elkies}. %
\begin{enumerate}
\item For a given prime $ℓ$, construct torsion bases $E[ℓ^k]$ and
  $E'[ℓ^k]$, where $k$ is chosen so that $ℓ^{2k}> 4r$.
\item Perform a change of basis so that $π$ acts on $E[ℓ^k]=〈P,Q〉$
  like a diagonal matrix $\mat{λ&0\\0&μ}$, with $λ≠μ$; do the same for
  $E'[ℓ^k]=〈P',Q'〉$. %
  If this is not possible, either $ℓ$ is not an Elkies prime, or we
  have computed $T_ℓ(E)$ to too low a precision (i.e., we need to
  choose a larger $k$). %
  In either case, we can decide to change prime $ℓ$ and start again,
  or to increase $k$ up to an acceptable bound.
\item For each diagonal matrix $M$ in $\GL_2(ℤ/ℓ^kℤ)$, interpolate the
  isogeny that maps $(P,Q)^t$ to $M(P',Q')^t$. %
  If this results in a rational isogeny of degree $r$, return it and
  stop.
\end{enumerate}

Pretty simple, huh? %
Well, now it is time to look at what we swept under the rug. %
So far we have spoken of ``constructing $E[ℓ^k]$'' as if this was an
easy thing to do. %
However the attentive reader will have noticed that $E[ℓ^k]$ may be
not (entirely) contained in $E(\F_q)$, and indeed it will almost never
be in the context of our algorithm. %
Thus, we first need to compute the smallest field extension of $\F_q$
where $E[ℓ^k]$ is going to be defined. %
We ``ascend'' level by level: first computing $E[ℓ]$, then $E[ℓ^2]$,
and so on until we reach $E[ℓ^k]$. %
Each step will require factoring some polynomials, in general of
degree $ℓ$, leading to the construction of a \emph{tower of
  extensions} on top of $\F_q$. %
Performing computations in towers of field extensions in optimal time
is a delicate task, requiring a great deal of computer algebra
techniques that we shall explore in the next chapter.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Perspectives}

\paragraph{Point counting.}
The \emph{raison d'être} of the explicit isogeny problem lies in
improving Schoof's point counting algorithm. %
In this chapter, we have not succeeded in improving its complexity,
and, to be completely honest, we have not even tried: any solution to
the explicit isogeny problem wanting to improve upon the
Elkies-Lercier-Sirvent algorithm needs to get rid of the modular
polynomial first. %
Indeed, even assuming an optimal algorithm%
\footnote{Quasi-optimal algorithms for computing modular polynomials
  do exist, see~\cite{enge09,sutherland10:modpol}} %
to compute $Φ_ℓ$, simply storing its coefficients requires $O(ℓ^3)$
bits, that become $O(ℓ^2\log p)$ after reducing modulo $p$. %

A possible way around would be an algorithm to compute $Φ_ℓ\mod p$
directly, without computing its integer coefficients first; however
the best algorithm for this~\cite{sutherland10:modpol}, a
multi-modular approach exploiting the structure of isogeny volcanoes,
only achieves quasi-optimal storage, but still requires $\tildO(ℓ^3)$
binary operations. %
Even better, one could compute $Φ_ℓ(j(E), y)$ directly, as Sutherland
does~\cite{sutherland2013evaluation}, however even for this problem we
only have an algorithm with quasi-optimal storage, but the same cubic
complexity. %

The same problem is felt, even more strongly, for curves of higher
genus. %
Indeed, even for the case of genus two curves, modular polynomials are
so
unwieldy~\cite{gaudry2000algorithmique,dupont2006moyenne,Broeker2009,milio_2015,milio:hal-01520262}
that they do not allow improving upon the basic Schoof-Pila
algorithm~\cite{pila90}. %

To the present day, the only known techniques to enumerate isogenous
curves of a fixed degree are based on factoring the division
polynomial or the modular polynomial. %
The techniques of this chapter do not seem to help. %
I am personally rather pessimistic on the possibility of improving the
SEA algorithm using Tate's isogeny theorem alone, however it is
certainly interesting to try to combine it with other ideas, in the
hope of getting a breakthrough in point counting, especially for
higher genus curves.

\paragraph{Couveignes' algorithm.}
Moving to Problem~\ref{prob:expl-isog-2} and to the ``$ℓ$-adic
Couveignes' algorithm'' presented in the previous section, even though
we know that it does not improve the asymptotic complexity of point
counting, it would still be interesting to know for which parameters
it improves SEA in practice, and by how much. %

Related to this, a goal that looks realistic would be to lift the
restriction to Elkies primes in the algorithm; hopefully having it run
in quadratic time for any elliptic curve. %
To be more precise, our paper uses~\cite{Shparlinski2014} to show that
one can find an Elkies prime $ℓ=O(\log q)$ for almost all finite
fields $\F_q$ and curves $E/\F_q$. %
In his PhD thesis~\cite{hugounenq:tel-01635463}, C.~Hugounenq
partially solves this problem by giving a quadratic time algorithm
when $\leg{Δ_π}{ℓ}=-1$, i.e. when $ℓ$ is an Atkin prime and the
corresponding volcano has height 0. %
This allows him to prove the existence of a quadratic algorithm for
any elliptic curve, however it does not improve upon the bound
$ℓ=O(\log q)$. %
A quadratic algorithm working with any $ℓ$ would considerably improve
the complexity in $\log q$, and would also be much more practical and
easy to implement. %

It is tempting to look for a variant of Couveignes' algorithm with
sub-quadratic complexity, possibly even quasi-linear. %
The techniques developed in this chapter do not seem capable of
breaking the quadratic barrier, and this looks somehow intrinsic to
Tate's theorem. %
My guess is that, if it was possible to obtain a sub-quadratic variant
of Couveignes' algorithm, bad things would start happening for the
cryptosystems presented in Chapter~\ref{cha:crypto}, at least those
based on complex multiplication. %

Computing isogenies of supersingular curves would be another obvious
extension of Couveignes' algorithm. %
Couveignes' original algorithm simply does not apply to supersingular
curves, because $p^k$-torsion groups are trivial. %
Our $ℓ$-adic algorithm is easily adapted to supersingular curves
defined over $\F_p$, because, as we shall see, their Frobenius
endomorphism behaves similarly to that of ordinary curves; however it
does not achieve the desired complexity for general supersingular
curves. %
This is deeply related to the differences between the CSIDH and SIDH
protocols presented in Chapter~\ref{cha:crypto}, and their security.

\paragraph{Computing endomorphism rings.}
Kohel's original motivation for defining depth and direction was to
compute the endomorphism ring of an ordinary curve $E/\F_q$, a problem
strictly harder than point counting. %
Indeed, knowing $\#E$ determines $π$, which in turn determines $ℚ(π)$;
the only thing that is left to know, then, is the depth of $E$ in each
of the $ℓ$-volcanoes, for $ℓ^2$ dividing $Δ_π$. %
The problem with this is that $ℓ$ is potentially as large as
$O(\sqrt{q})$, and thus any algorithm computing $ℓ$-isogenies is bound
to have exponential complexity. %
An alternative approach using isogenies of smooth degree, due to
Bisson and Sutherland~\cite{bisson+sutherland11}, achieves
sub-exponential complexity. %

The effective versions of Tate's theorem give an alternative way to
determine the depth of an elliptic curve, one that potentially has
polynomial complexity in $\log q$. %
However, the methods proposed in this chapter to compute $π|T_ℓ(E)$
involve computing the $ℓ$-torsion, and thus have polynomial complexity
in $ℓ$. %

I find it unlikely that the techniques of this chapter could improve
significantly the computation of endomorphism rings, but let's be
optimistic and imagine a sci-fi scenario. %
In the same way that Schoof's algorithm computes the trace of $π$
modulo many small primes to find its value in $ℤ$, one may hope that
there is some sort of ``global'' description of $π|\prod_ℓ'T_ℓ(E)$ that
can be reconstructed from $π|T_{ℓ'}(E)$ for many small primes $ℓ'$. %
If this description could be computed in polynomial time, then we
would have a polynomial time algorithm for the endomorphism ring. %

Besides science-fiction, the way isogeny volcanoes interact for
different primes has received very little attention so far, the only
work I am aware of being~\cite{MOODY20125249}. %
I believe that some interesting algorithmic ideas could derive from
studying how the knowledge of $π|T_ℓ(E)$ affects the computation of
$π|T_{ℓ'}(E)$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapart{art/ballon-color}
\chapter{Altimetry}
\label{cha:fpbar}
\epigraph{\it --- L'atmosphère terrestre a une hauteur de six mille
  toises, répondit le docteur. Avec un vaste ballon, on irait
  loin. C'est ce qu'ont fait MM. Brioschi et Gay-Lussac; mais alors
  le sang leur sortait par la bouche et par les oreilles. L'air
  respirable manquait. Il y a quelques années, deux hardis Français,
  MM. Barral et Bixio, s'aventurèrent aussi dans les hautes régions;
  mais leur ballon se déchira\dots
  
  --- Et ils tombèrent? demanda vivement Kennedy.

  --- Sans doute! mais comme doivent tomber des savants, sans se faire
  aucun mal.}{--- Jules Verne,\\Cinq semaines en ballon}

In the previous chapter we saw how to determine the structure of an
isogeny volcano by looking at the way the Frobenius endomorphism acts
on the Tate module. %
To effectively perform the computation, we need to approximate the
Tate module by projecting it onto a torsion group of order, say,
$ℓ^k$. %
Even this finite group, however, may not be defined over the base
field. %
It is then natural to construct \emph{towers of extensions fields},
over which increasingly larger torsion groups are defined. %

But why stop at towers? %
This chapter is devoted to techniques to ``ascend'' in \emph{lattices
  of extension fields}, possibly up to the full algebraic closure
$\bar{\F}_p$. %
The structure of $\bar{\F}_p$ is simple enough that we will not need
more than the basic theory of cyclotomic extensions. %
Instead, we will concentrate our efforts on looking for asymptotically
optimal algorithms, discovering on our path a rich palette of
algorithmic ideas. %

After learning about representations of finite fields and algorithms
to compute irreducible polynomials, we will explore two radically
different paradigms to represent the algebraic closure of $\F_p$, both
being currently used in computer algebra systems. %
On one side, we will have lattices of finite fields represented by
families of \emph{special} polynomials, the most well known example
being the family of Conway polynomials, introduced in the GAP
system~\cite{GAP4}, and then adopted by Magma~\cite{MAGMA} and
SageMath~\cite{Sage}. %
On the other side, we will have lattices of \emph{arbitrarily
  represented} finite fields, such as those used by Magma. %
The fundamental tool for these will be an \emph{isomorphism
  algorithm}, we shall thus learn about the two main existing
families: the first one, due to Lenstra~\cite{LenstraJr91} and
Allombert~\cite{Allombert02}, based on the theory of Kummer
extensions; the second one, due to Pinch~\cite{Pinch} and
Rains~\cite{rains2008}, based on Gaussian periods. %


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

\section{Computing irreducible polynomials}

From now on, $\F_p$ is a finite field of prime order. %
Much of what we are going to present is easily generalized to
non-prime fields, however we will stick to prime fields for
simplicity, and refer to the appendix the reader interested in
the general case. %

Since this chapter is chiefly about complexity, we need to agree on a
unit of measurement. %
The field $\F_p$ is typically represented as the ring of integers
modulo $p$, using $\log p$ bits per element. %
Addition, subtraction and multiplication modulo $p$ can all be
performed in $\tildO(\log p)$ binary operations using asymptotically
fast integer multiplication and Euclidean division, while field
inversion can be computed at the same asymptotic cost using a fast
extended Euclidean algorithm (see~\cite{vzGG} for a detailed
account). %
\emph{Zech logarithms} are another commonly used representation for
finite fields of small size: elements of $\F_p$ are represented as
powers of a generator, making it relatively cheap to multiply and
invert elements, whereas additions are computed by a lookup in a table
with $O(p)$ entries. %

Even though in practice any representation has noticeably different
costs for the various arithmetic operations, it will be convenient to
abstract from the actual implementation of $\F_p$ and measure
complexities in the \emph{algebraic model}, i.e., counting every field
operation as $O(1)$. %
Given a complexity in the algebraic model, a relatively accurate
estimate of the binary complexity can be obtained by multiplying by
$\log p$ (and ignoring polynomial terms in $\loglog p$). %

The universally employed way to represent a field extension $\F_{p^n}$
is as a quotient of the polynomial ring $\F_p[X]$ by a monic
irreducible polynomial $f(X)$ of degree $n$. %
In this representation, much like in the modular integers case, all
arithmetic operations can be performed in $\tildO(n)$ elementary
algebraic operations using fast polynomial multiplication, Euclidean
division, and extended Euclidean algorithm (see again~\cite{vzGG}). %
Most popular software libraries for number theory, e.g.,
Flint~\cite{Hart2010}, NTL~\cite{shoup2003ntl}, PARI/GP~\cite{Pari},
Magma~\cite{MAGMA}, use this representation%
\footnote{Givaro~\cite{givaro} is one notable exception, employing
  Zech logarithms. %
  All of the mentioned libraries, with the exception of Magma, are
  used by SageMath~\cite{Sage}.}, %
and a considerable amount of effort has been spent in optimizing it. %
Hence this representation, that we shall call \emph{univariate}, is
the best choice both from an asymptotical and a practical point of
view. %

Of course, to employ this representation, we need an algorithm to
compute irreducible polynomials of arbitrary degree. %
Three different approaches are known. %

The first one, and the simplest, consists in taking random monic
polynomials until an irreducible one is found. %
The density of irreducible polynomials of a given degree $n$ is
$\sim 1/n$, thus this approach will lead to an irreducible polynomial
in $O(n)$ tries on average. %
Testing irreducibility of random polynomials can be done in
$\tildO(n\log p)$ operations on average, using Ben-Or's
algorithm~\cite{Ben-Or1981,10.1007/978-3-642-60539-0_27}, thus in
total this approach has a quasi-quadratic dependency on $n$. %
This is the most commonly implemented method, available in Magma,
SageMath, etc.

The second method is due to Adleman and
Lenstra~\cite{Adleman-Lenstra}, and implemented, as far as I know,
only in PARI/GP\footnote{And thus also available in SageMath.}. %
It is based on the properties of cyclotomic polynomials, and is
similar in spirit to Rains' algorithm presented in
Section~\ref{sec:isom-finite-fields}. %
Adleman and Lenstra show that their algorithm takes deterministic
polynomial time, under the generalized Riemann hypothesis, albeit with
a quite large exponent. %
However, the algorithm is quite efficient in practice, and the average
case complexity of the variant implemented in PARI/GP is similar to
that of factoring a degree $n$ polynomial over $\F_p$.%
\footnote{We are not aware of any published formal analysis of the
  PARI/GP variant, however we believe that the average-case complexity
  is (heuristically) dominated by the cost of factoring a cyclotomic
  polynomial of degree $O(n\log n)$. %
  See also Section~\ref{sec:isom-finite-fields}} %

The third method is due to Shoup~\cite{Shoup_1990,shoup93,shoup94},
later extended by Couveignes and
Lercier~\cite{couveignes+lercier11,DeDoSc13}. %
It uses a variety of algorithms, that we shall discuss in
Section~\ref{sec:spec-famil-irred}. %
Using the best available routines, it can compute an irreducible
polynomial in $\tildO(n(\log p)^5)$ operations on average, but
trade-offs are available if the cost in $\log p$ is deemed too high. %
We are not aware of any computer algebra software implementing this
method, probably owing to the relative novelty of the method, and to
its intricacies. %

We note that it is an open problem to give an unconditionally
deterministic algorithm to compute irreducible polynomials of
arbitrary degree. %
The closest to this is Shoup's first algorithm~\cite{Shoup_1990}: it
consists of reduction from the problem of finding irreducible
polynomials to that of polynomial factoring, and can be made fully
deterministic using Berlekamp's deterministic factoring
algorithm~\cite{berlekamp1970factoring}; however Berlekamp's algorithm
has an exponential dependency in $\log p$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

\section{From one extension to the algebraic closure}

In many contexts, such as when manipulating geometrical objects, it is
natural to work in many extensions of $\F_p$ at once. %
We may push this to the limit: the algebraic closure $\bar{\F}_p$ is
the (infinite) reunion of all the finite extensions of $\F_p$; it is
thus sufficient to represent all finite extensions of $\F_p$ in a
\emph{compatible} way in order to represent $\bar{\F}_p$.

A natural choice to represent a collection of extensions of $\F_p$ is
as a \emph{towers of extensions}: for example, $\F_{p^2}$ may be
represented as $\F_{p}[X_1]/f_1(X_1)$, then $\F_{p^6}$ as
$\F_{p^2}[X_2]/f_2(X_2)$, and so on. %
In general, the polynomial $f_i$ will have coefficients over the
previous field. %
``Flattening'' the tower, we may rewrite the system of extension
fields as a quotient
\begin{equation}
  \label{eq:triangular}
  \F_p[X_1,\dots,X_k] /
  \left|\begin{array}{l}
          X_k^{n_k} - \tilde{f}_k(X_1,\dots,X_k),\\
          \qquad\vdots\\
          X_1^{n_1} - \tilde{f}_1(X_1),
        \end{array}\right.
\end{equation}
where the $i$-th field in the tower is identified with the subring
generated by $X_1,\dots,X_i$. %
The polynomial ideal in Eq.~\eqref{eq:triangular} is a special case of
a (zero-dimensional) \emph{triangular set}, and an extensive
literature is devoted to computing modulo them, both in dimension
0~\cite{LEBRETON2015230,PoSc13b}, and in higher
dimension~\cite{Aubry:1999:TTS:2947511.2947551}. %
Performing arithmetic operations modulo triangular sets incurs an
intrinsic penalty, exponential in the number $k$ of variables, that an
ordinary univariate representation does
not~\cite{canny+kaltofen+yagati89,li+moreno+schost07,vanderHoeven:2004:TFT:1005285.1005327}. %

To recover the quasi-optimal performance of the univariate
representation, we may seek a \emph{change of order}%
\footnote{The name ''change of order'' comes from the theory of
  Gröbner bases, it is indeed equivalent to a change of order from
  lexicographic to inverse lexicographic.} %
algorithm to rewrite the quotient as
\begin{equation*}
  \F_p[X_1,\dots,X_k] /
  \left|\begin{array}{l}
          X_k^e - g_n(X_k),\\
          \qquad\vdots\\
          X_2 - g_2(X_k),\\
          X_1 - g_1(X_k).
        \end{array}\right.
\end{equation*}
This representation goes under various names, such as \emph{rational
  univariate representation}~\cite{rouiller99} and \emph{geometric
  resolution}~\cite{giusti+lecerf+salvy01}. %
Using this representation, we can efficiently perform arithmetic in
the top level of the tower, and we can still identify the $i$-th
intermediate fields as being generated by $X_i$, or equivalently by
the polynomial expression $g_i(X_k)$. %

However, our special instance enjoys many special properties that
general triangular sets do not, and we wish to exploit them. %
On the other hand, the tower of extensions paradigm is not adapted to
all situations: for example, a field $\F_{p^{mn}}$ with $m∧n=1$ can be
seen both as an extension of $\F_{p^n}$ and as one of $\F_{p^m}$. %

Ideally, we would like to have a \emph{data structure} to represent
\emph{arbitrary collections} of extensions of $\F_p$, in such a way
that any extension is represented in optimal space (i.e., $O(n)$
coefficients for an element of an extension of degree $n$), and that
arithmetic operations are performed in quasi-optimal time (i.e.,
$\tildO(n)$ operations). %
To this end, we now name several useful properties that we are going
to seek.

\begin{description}
\item[\emph{Compatibility:}] For any pair of extensions $\F_p⊂k⊂K$,
  there is an algorithm that takes an element $x∈k$ and outputs its
  representation as an element of $K$. Reciprocally, there is an
  algorithm that tests whether an element $y∈K$ belongs to $k$, and in
  that case outputs its representation as an element of the smaller
  field. %
\item[\emph{Incrementality:}] The data associated with an extension
  (e.g., its irreducible polynomial, change-of-basis matrices, \dots)
  must be computable efficiently and \emph{incrementally}, i.e.,
  adding a new field extensions to the collection does not require
  recomputing data for all extensions already represented. %
\item[\emph{Uniqueness:}] Any extension is determined by an
  irreducible polynomial whose definition only depends on the
  characteristic $p$ and the degree of the extension. %
\end{description}

Note that both incrementality and uniqueness are optional, however the
former is necessary to represent the algebraic closure effectively,
and the latter provides a \emph{standard} way to represent it. %
More advanced features, such as computing normal bases, evaluating
Frobenius morphisms, etc., are also (terribly) interesting, but they
are out of the scope of this document. %

The reader may be surprised to learn that no such representation is
known! %
The difficulty is not a theoretical one: besides the problem of
finding irreducible polynomials, any other question is amenable to
linear algebra, as Lenstra showed~\cite{LenstraJr91}. %
Instead, the difficulty is to satisfy all requirements in an
efficient, possibly quasi-optimal, manner. %

Various solutions have been deployed in practice in computer algebra
systems such as Magma and SageMath, however none of these is
especially efficient. %
In the next sections we shall explore the various available
constructions, and possible research avenues. %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

\section{Special families of irreducible polynomials}
\label{sec:spec-famil-irred}

Among all irreducible polynomials, which ones are best suited to
represent a collection of finite extensions of $\F_p$, or potentially
the collection of \emph{all} finite extensions of $\F_p$? %
This fascinating question, investigated by many, has no single answer:
indeed, depending on what is meant by ``best'', different solutions
are possible. %

\paragraph{Conway polynomials.}
One of the most famous constructions is that of \emph{Conway
  polynomials}. %
The main feature of Conway polynomials is \emph{norm compatibility}:
the norm map $\F_{q^n}→\F_{q^m}$ is a surjection from the roots of the
$n$-th Conway polynomial to the roots of the $m$-th Conway polynomial,
whenever $m$ divides $n$. %

Norm compatibility is easy to achieve for a fixed collection
$\mathcal{F}$ of finite extensions of $\F_p$: let $K/\F_p$ be the
smallest finite field containing all fields in $\mathcal{F}$, let $η$
be a primitive element of $K$, i.e., a generator of the multiplicative
group $K^×$, then the Conway polynomial of a field $k⊂K$ is defined as
the minimal polynomial of $N_{K/k}(η)$, where $N_{K/k}$ is the norm
map. %
However, Conway polynomials have two other goals: incrementality and
uniqueness. %
This leads to the following definition.

\begin{definition}[Conway polynomial]
  Let $p$ be a prime and $n>1$ an integer. %
  The \emph{Conway polynomial} $C_{p,n}$ is the
  \emph{lexicographically smallest} monic irreducible polynomial of
  degree $n$ satisfying the following conditions:
  \begin{itemize}
  \item \emph{Primitivity:} $C_{p,n}$ is primitive (i.e., its roots
    generate the multiplicative group $\F_{p^n}^×$);
  \item \emph{Norm compatibility:} If $m$ divides $n$, then
    $C_{p,m}\left(X^{\frac{p^n-1}{p^m-1}}\right) = 0 \mod C_{p,n}$.
  \end{itemize}
\end{definition}

The ``lexicographically smallest'' condition is required to ensure
uniqueness; it is typically defined by writing $f∈\F_p[X]$ as
\begin{equation*}
  f = \sum_{i=0}^n (-1)^{n-i} f_i x^i,
  \qquad\text{with $0≤f_i<p$,}
\end{equation*}
and taking the lexicographic order on the words $f_n\dots f_0$.

Conway polynomials were defined by Parker%
\footnote{According to Lübeck~\cite{Luebeck}.}, %
who named them in honor of John Conway and his famous book ``On
Numbers and Games''~\cite{Conway:ONAG2000}; their existence was shown
by Nickel~\cite{Nickel1988}. %
They were first adopted by the computer algebra system GAP~\cite{GAP4}
as a default representation for finite fields. %
They are typically computed by exhaustive search over all irreducible
polynomials, or by a slightly better algorithm due to Heath and
Loehr~\cite{heath+loehr99}. %
Given the huge computational cost involved in finding them, they are
usually precomputed; tables of Conway polynomials are available in any
major computer algebra system.%
\footnote{Most computer algebra systems switch to other methods when
  precomputed Conway polynomials are not available. %
  An interesting exception is SageMath (since version
  5.13~\cite{Roe2013}), that defines \emph{pseudo-Conway polynomials}
  by dropping the ``lexicographically first'' requirement, and
  computes them on the fly whenever a true Conway polynomial is not
  available in the tables. %
  The approach is notoriously slow: computing a pseudo-Conway
  polynomial for $\F_{p^{30}}$ takes in the order of seconds, already
  for $p>1000$; compare this to the milliseconds needed to compute a
  random irreducible polynomial of the same degree.} %

We note that Conway polynomials are not especially good to represent
embeddings: given an element of $\F_{p^m}$ represented as
$a(X) \bmod C_{p,m}(X)$, its image in $\F_{p^n}$, for $m\mid n$, is
computed as $a(X^{(p^n-1)/(p^m-1)})\bmod C_{p,n}(X)$, requiring very
large modular exponentiations; while there are algorithms to perform
this computation in $O(n^{1+o(1)})$ operations~\cite{KeUm11}, they are
known to be very inefficient in practice. %

\begin{figure}
  \centering
  \begin{tikzpicture}[scale=0.8]
    \coordinate (T2) at (-2, 0.5);
    \draw
    (0,0) node (Fq)  {$\F_p$}
    ++(T2) node (Fq2) {$\F_{p^2}$}
    ++(T2) node (Fq4) {$\F_{p^4}$}
    ++(T2) node (Fq2l) {$\F_p^{(2)}$};
    % ---------------------
    \coordinate (T3) at (-0.7, 2);
    \draw
    ++(T3) node (Fq3) {$\F_{p^3}$}
    ++(T3) node (Fq9) {$\F_{p^9}$}
    ++(T3) node (Fq3l) {$\F_p^{(3)}$};
    % ---------------------
    \coordinate (T5) at (0.7, 2);
    \draw
    ++(T5) node (Fq5) {$\F_{p^5}$}
    ++(T5) node (Fq25) {$\F_{p^{25}}$}
    ++(T5) node (Fq5l) {$\F_p^{(5)}$};
    % ---------------------
    \coordinate (Tl) at (2, 1);
    \draw
    ++(Tl) node (Fql) {$\F_{p^ℓ}$}
    ++(Tl) node (Fql2) {$\F_{p^{ℓ^2}}$}
    ++(Tl) node (Fqll) {$\F_p^{(ℓ)}$};
    % ---------------------
    \draw[every node/.style=dotstyle]
    (Fq) ++(Fq2) ++(Fq3) node (dot1) {}
    (Fq) ++(Fq4) ++(Fq3) node (dot2) {}
    (Fq) ++(Fq2) ++(Fq5) node (dot3) {}
    (Fq) ++(Fq3) ++(Fq5) node (dot4) {}
    (Fq) ++(Fq3) ++(Fql) node (dot5) {}
    (Fq) ++(Fq5) ++(Fql) node (dot6) {};
    % ---------------------
    \draw 
    (Fq) 
    edge[edgetower] (Fq2)
    edge[edgetower] (Fq3)
    edge[edgetower] (Fq5)
    edge[edgetower] (Fql)
    (Fq2)
    edge[edgetower] (Fq4)
    edge[edgecomp] (dot1)
    (Fq4)
    edge[edgetower, dotted] (Fq2l)
    edge[edgecomp] (dot2)
    (dot1)
    edge[edgecomp] (dot2)
    (Fq3)
    edge[edgetower] (Fq9)
    edge[edgecomp] (dot1)
    edge[edgecomp] (dot4)
    (Fq9)
    edge[edgetower, dotted] (Fq3l)
    (Fq5)
    edge[edgetower] (Fq25)
    edge[edgecomp] (dot4)
    edge[edgecomp] (dot6)
    (Fq25)
    edge[edgetower, dotted] (Fq5l)
    (Fql)
    edge[edgetower] (Fql2)
    edge[edgecomp] (dot6)
    (Fql2)
    edge[edgetower, dotted] (Fqll)
    (dot3)
    edge[edgecomp] (Fq2)
    edge[edgecomp] (Fq5)
    (dot5)
    edge[edgecomp] (Fq3)
    edge[edgecomp] (Fql);
  \end{tikzpicture}
  \caption{Lattice of extensions of $\F_p$.}
  \label{fig:fpbar}
\end{figure}

\paragraph{Primary towers.}
All other solutions are generalizations of Shoup's algorithm for
computing irreducible polynomials~\cite{Shoup_1990,shoup93,shoup94}. %

We start by restricting to \emph{primary towers of extensions}, i.e.,
towers of extensions of prime-power degree. %
Formally, for a prime $ℓ≠p$, define the \emph{$ℓ$-adic closure} of
$\F_p$ as the infinite field
$\F_p^{(ℓ)} = \bigcup_{i\ge 0}\F_{p^{ℓ^i}}$.

To represent $\F_p^{(ℓ)}$, we want to define an infinite family of
irreducible polynomials of degree $ℓ^i$ for $i>0$, and algorithms to
evaluate the corresponding embeddings
$\F_{p^{ℓ^{i-1}}}⊂\F_{p^{ℓ^{i}}}$. %

Here is a simple example: suppose that $ℓ$ divides $p-1$, then the
$ℓ$-th power map is not injective on $\F_p$, and thus $\F_p$ contains
$ℓ$-adic non-residues. %
Let $η$ be such a non-residue, then $X_i^{ℓ^i}-η$ is a family of
irreducible polynomials, and the embeddings between the fields
$\F_{p^{ℓ^i}}$ are easily defined by the relationship
$X_i^ℓ=X_{i-1}$. %
We may call this special case the ``Kummer case'', for obvious
reasons. %

Shoup's construction generalizes the Kummer case to an arbitrary prime
$ℓ$, by adjoining $ℓ$-th roots of unity to $\F_p$. %
The idea is to define an extension $\F_q=\F_p(ζ_ℓ)$ of the base field,
and then construct its $ℓ$-adic closure $\F_q^{(ℓ)}$. %
The sought closure is then identified to a subfield
$\F_p^{(ℓ)}⊂\F_q^{(ℓ)}$ using a projection map; this is illustrated below.
\begin{equation*}
  \begin{tikzpicture}
    \draw
    (0,0) node(Q){$\F_p$}
    (-1,1) node(Q0){$\F_q=\F_p(ζ_ℓ)$}
    (1,1) node(K1) {$\F_{p^ℓ}$}
    (0,2) node(Q1) {$\F_{q^ℓ}$}
    (2,2) node(Koo) {$\F_p^{(ℓ)}$}
    (1,3) node(Qoo) {$\F_q^{(ℓ)}$};
    \draw (Q) edge node[auto]{\scriptsize$r$} (Q0)
              edge node[auto,swap]{\scriptsize$ℓ$} (K1)
          (K1) edge (Q1)
          (Q1) edge (Q0)
               edge[dashed] (Qoo)
          (Koo) edge[dashed] (K1)
               edge (Qoo);
  \end{tikzpicture}
\end{equation*}

Shoup explicitly computes $\F_q$ by factoring the $ℓ$-th cyclotomic
polynomial, then finds an $ℓ$-adic non-residue $η∈\F_q$, and defines
$\F_{q^{ℓ^i}}$ as $\F_q(X_i)/(X_i^{ℓ^i}-η)$. %
Then, a defining polynomial of $\F_{p^{ℓ^i}}$ is found by taking the
trace $\F_{q^{ℓ^i}}→\F_{p^{ℓ^i}}$ of the residue class of $X_i$, and
computing its minimal polynomial. %

Shoup's construction pays an intrinsic $O(ℓ)$ overhead, because of the
\emph{auxiliary extension} $\F_p(ζ_ℓ)$. %
To avoid this cost, Couveignes and Lercier's generalize the Kummer
case in a different direction. %

It is well known in number theory folklore that any algorithm that
uses purely multiplicative properties of $\F_p$ can be generalized by
replacing the multiplicative group $\F_p^×$ with a different algebraic
group $G(\F_p)$, e.g., the group of points of an elliptic curve
$E/\F_p$. %
This principle is the basis, for example, for Lenstra's elliptic curve
factoring method~\cite{lenstra87}. %
We shall see this principle applied over and over again in this
chapter. %

The Kummer case is based on the fact that the map $x↦x^ℓ$ is
surjective on $\bar{\F}_p$, but not on $\F_p$. %
Because of its geometric properties, its fibers are irreducible and
define irreducible polynomials $X^ℓ-η$ whenever $η$ is an $ℓ$-adic
non-residue. %
Does this ring a bell?

We saw at the beginning of this document that an isogeny $ϕ:E→E'$
is a degree $ℓ$ map, surjective on $E'(\bar{\F}_p)$, but not on
$E'(\F_p)$ whenever $\ker ϕ⊂E(\F_p)$. %
If we choose an elliptic curve $E/\F_p$ such that $π|E[ℓ]$ acts like
$\mat{1&0\\0&μ}$ for some $μ≠1\pmod{ℓ}$, then the isogeny $ϕ$
associated to the eigenvalue $1$ is not surjective, and its fibers are
irreducible. %

Couveignes and Lercier take random elliptic curves, and count their
points, until one with the desired Frobenius endomorphism is found. %
Then they compute the unique $ℓ$-isogeny $ϕ:E→E'$ with rational
kernel, using Vélu's formulas, and find a point $P∈E'(\F_p)$ not in
$ϕ(E(\F_p))$. %
The irreducible polynomial defining $\F_{p^ℓ}$ is then deduced from
the fiber $ϕ^{-1}(P)$, for example by projecting onto the $x$-axis. %
By iterating the process, we easily generalize to arbitrary primary
extensions $\F_{p^{ℓ^i}}$. %

The drawback of this technique is the high cost involved in the search
for a suitable elliptic curve: if $ℓ<p^{1/4}$ about one curve in $ℓ$
has the desired property~\cite{lenstra87,castryck+hubrechts13}, and
counting the number of points takes $\tildO((\log p)^5)$ operations
using Schoof's algorithm%
\footnote{This complexity bound could be improved using the
  Schoof--Elkies--Atkin algorithm, however this would add additional
  heuristic hypotheses to the construction.}. %
Hence, this construction is only practical for relatively small values
of $p$ and $ℓ$. %
Also, in general, $ℓ$ may be so large that no elliptic curve exists
with the desired properties. %
In this case Couveignes and Lercier propose extending the base field
$\F_p$ to an extension of degree $O(\log ℓ)$, and use the same
projection machinery as in Shoup's original construction. %
Although this trick salvages the asymptotic complexity of the method,
I am not sure anyone has ever dared implement it. %

So far, we have only mentioned the construction of the irreducible
polynomials, without talking about compatibility. %
In the work ``Fast Algorithms for $ℓ$-adic Towers over Finite Fields''
written with J.~Doliskani and É.~Schost~\cite{DeDoSc13}, we provide
algorithms to efficiently evaluate embeddings, both for Shoup's and
for Couveignes and Lercier's construction, and we also add
incrementality to the latter. %
The techniques are relatively simple generalizations of the Kummer
case, leveraging fast algorithms for polynomial composition and
decomposition, and we will not detail them. %
Suffice to say that they are very efficient, both asymptotically and
in practice, and achieve compatibility in quasi-linear time for the
Couveignes--Lercier construction. %
Experiments in~\cite{DeDoSc13} show that they beat other techniques by
orders of magnitude, in particular when constructing a primary tower
with many levels\footnote{Gains are already remarkable for
  $\F_{p^{81}}$}. %

Couveignes and Lercier's technique, and thus our extension, does not
naturally provide uniqueness: this depends intrinsically on the random
choices of elliptic curves. %
Although it would be possible to fix the choices of the algorithm in a
deterministic way, this feels even less natural than for Conway
polynomials. %
A better option is to fix the choices made by Shoup's construction in
a deterministic way; this is exactly what Lenstra and de Smit do
in~\cite{lenstra+desmit08-stdmodels}, with a special focus on
deterministic algorithms. %
However, to the best of my knowledge, no one has ever tried
implementing this construction, that looks mostly of theoretical
interest. %

A few words on the case $ℓ=p$, to finish. %
We can define $\F_p^{(p)}$ in the same way as we have defined the
$ℓ$-adic closure, however none of the techniques described so far
applies to this case. %
The construction of irreducible polynomials of degree $p^i$ using
Artin-Schreier theory is folklore, and already present
in~\cite{Adleman-Lenstra}. %
The related algorithms for computing embeddings are developed
in~\cite{df+schost09,df+schost12}.

\paragraph{Composita.}
Once we have $ℓ$-adic closures for any $ℓ$, we need to ``glue'' them
together to obtain the algebraic closure. %
Formally, $\bar{\F}_p$ is isomorphic to the tensor product
$⨂_{ℓ} \F_p^{(ℓ)}$, where $ℓ$ runs over all primes. %
This suggests representing an extension of degree
$n=ℓ_1^{e_1}\cdots ℓ_k^{e_k}$ as a quotient
\begin{equation}
  \label{eq:tensor}
  \F_p[X_1,\dots,X_k] / 
  \left|\begin{array}{l}
          X_k^{ℓ_k^{e_k}} - f_k(X_k),\\
          \qquad\vdots\\
          X_1^{ℓ_1^{e_1}} - f_1(X_1);
        \end{array}\right.
\end{equation}
however, arithmetic operations in this representation incur the same
penalty as triangular sets. %

The building block to switch to a rational univariate representation
will be an algorithm to compute \emph{composita} with explicit
embeddings. %
Formally, given two extensions fields $\F_{p^m}$ and $\F_{p^n}$, with
$m∧n=1$, we want to compute a univariate representation for the field
$\F_{p^{mn}}$, together with efficient algorithms for evaluating the
embeddings $\F_{p^m}\hookrightarrow \F_{p^{mn}}$ and
$\F_{p^n}\hookrightarrow \F_{p^{mn}}$. %
By applying this construction recursively, we can represent an
arbitrary tensor product of primary extensions. %

The construction of an irreducible polynomial of degree $mn$ is
folklore, and was already used by Shoup~\cite{Shoup_1990}. %
Given two separable polynomials $f$ and $g$, their \emph{composed
  product} is the polynomial
\begin{equation*}
  (f⊗g)(X) = \prod_{f(α)=0}\prod_{g(β)=0} (X - αβ).
\end{equation*}
We similarly define the \emph{composed sum} as the polynomial whose
roots are the sums of the roots of $f$ and $g$. %
It is well known that, if $f,g∈\F_p[X]$ are irreducible polynomials of
coprime degree, then both their composed sum and composed product are
irreducible~\cite{BrCa87}.%
\footnote{The hypothesis that $f,g$ have coefficients in a finite
  field is important. %
  For example, only the composed sum is necessarily irreducible if the
  polynomials have rational coefficients.} %
Both polynomials can be computed in $\tildO(mn)$ operations using
algorithms in~\cite{BoFlSaSc06}, and both have been used to construct
irreducible polynomials of arbitrary degree. %

The less evident part is the evaluation of the embeddings. %
In ``Fast Arithmetic for the Algebraic Closure of Finite Fields''
written with J.~Doliskani and É.~Schost~\cite{DeDoSc2014}, and
included in the appendix, we develop new techniques for embeddings of
composita constructed through composed products. %
Our techniques are purely algebraic, and apply to any base field,
however they are most interesting in practice to compute in composita
of finite fields. %

The main technical ingredient of our work is a representation of
finite field elements using a pair of monomial/dual bases, drawing
from previous work of Shoup~\cite{shoup94,shoup95,shoup99} and Bostan,
Salvy and Schost~\cite{bostan+salvy+schost03}. %

If $\F_{p^m}$ is represented as $\F_p[X]/f(X)$, we define its
\emph{monomial basis} as $(1,X,\dots,X^{m-1})$. %
The associated \emph{dual basis} is $(X_0^*,X_1^*,\dots,X_{m-1}^*)$,
where $X_i^*$ are defined by
\begin{equation*}
  \Tr(X^jX_i^*)_k = \begin{cases}
    1 &\text{if $i=j$,}\\
    0 &\text{otherwise,}
  \end{cases}
\end{equation*}
$\Tr$ denoting the trace from $\F_{p^m}$ to $\F_p$. %
Given the polynomial $f$, conversions between the monomial and the
dual basis can be performed very efficiently at a cost of $\tildO(n)$
operations, thus we allow ourselves to switch freely between the two
representations. %

Now, let $\F_{p^m},\F_{p^n}$ and $\F_{p^{mn}}$ be represented as in
the diagram
\begin{equation*}
  \begin{tikzpicture}
    \draw
    (0,0) node(Fp) {$\F_p$}
    (-1,1) node[anchor=east](Fpm) {$\F_p[X]/f(X) =  \F_{p^m}$}
    (1,1) node[anchor=west](Fpn) {$\F_{p^n} = \F_p[Y]/g(Y)$}
    (0,2) node(Fpmn) {$\F_{p^{mn}} = \F_p[Z]/(f⊗g)(Z)$};
    \draw
    (Fp) edge (Fpm) edge (Fpn)
    (Fpmn) edge (Fpm) edge (Fpn);
  \end{tikzpicture}
\end{equation*}
with the natural embedding defined by $Z=XY$. %
We seek an algorithm for the following operation: given $b∈\F_{p^m}$
and $c∈\F_{p^n}$, compute $bc∈\F_{p^{mn}}$. %
Note that this gives a way to evaluate both embeddings, by fixing
either $c=1$ or $b=1$. %

The key observation is that the product $bc$ is computed as a
component-wise product in the dual bases of the respective fields. %
The embedding algorithm is thus (almost) as simple as converting both
$b$ and $c$ to the respective dual bases, multiplying
component-by-component, and converting back to the monomial basis of
$\F_{p^{mn}}$. %
We refer to the appendix for further details. %

There is another, quite technical, ingredient to the paper, that we
have mostly ignored so far. %
Evaluating embeddings is only half of the job: we also want to
evaluate the (partial) inverse maps, or, more generally, projections
$\F_{p^{mn}}→\F_{p^m}$ and $\F_{p^{mn}}→\F_{p^n}$ that, when
composed with the embeddings, yield the identity map. %

A general \emph{mantra} states that, whenever a field isomorphism
$ϕ:k→K$ can be evaluated at a certain cost, the inverse map $ϕ^{-1}$
can evaluated at the same cost (see~\cite[§8.2]{ffisom-long} for a
precise statement). %
In our specific instance, let $b∈\F_{p^m}$, and let $M_b$ be the
matrix of the map $c↦bc$, for any $c\in\F_{p^n}$,
in the \emph{dual bases} of $\F_{p^n}$ and $\F_{p^{mn}}$. %
Direct calculation shows that $M_b^t$ is the matrix of the map
$a↦\Tr_{\F_{p^{mn}}/\F_{p^n}}(ab)$ in the \emph{monomial bases} of
$\F_{p^{mn}}$ and $\F_{p^n}$; thus, if
$\Tr_{\F_{p^{mn}}/\F_{p^n}}(b)=1$, the matrix $M_b^t$ is a partial
inverse to $M_b$ (albeit in a different basis).%
\footnote{I feel so guilty for shrinking one of my favorite tricks to
  one single paragraph. %
  Really, go read~\cite[§8]{ffisom-long}, please!} %
% TODO: check the scalars

To obtain an algorithm from this observation, we use a technique
called \emph{transposition
  principle}~\cite{shoup99,bostan+lecerf+schost:tellegen},
transforming an algorithm to evaluate $M_b$ into one to evaluate
$M_b^t$ \emph{at the same cost}. %
Said otherwise, we derive an efficient projection algorithm by
\emph{transposing} the embedding one. %

In conclusion, our techniques allow to compute embeddings and
projections of composita in quasi-optimal time. %
They also allow to evaluate vector space isomorphisms (e.g.,
$\F_{p^{mn}}≃\F_{p^m}^n$ with respect to the monomial or the dual
basis) with the best known complexity, although not in quasi-optimal
time. %
By combining these techniques with any technique for primary towers,
we obtain a representation for $\bar{\F}_p$, unique if the
representation of primary towers is. %
Unfortunately, since we do not know how to evaluate vector space
isomorphisms in quasi-optimal time, we inherit the same unsatisfactory
complexity for any computation in $\bar{\F}_p$. %
Lifting this restriction is one of the problems that torments me. %


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

\section{Isomorphisms of finite fields}
\label{sec:isom-finite-fields}

Special (compatible) families of irreducible polynomials are a
fascinating topic, however they are not a universal solution. %
In some circumstances, we may not have the choice of the polynomial
representing a field extensions; this happens quite often in computer
algebra systems that let the user choose their own polynomial. %

Isomorphism algorithms let us lift this restriction: using them, a
computer algebra system may internally represent finite fields with
special polynomials, while letting the user work with an isomorphic
copy defined by a polynomial of their choice. %
In the next section we shall also see how isomorphism algorithms
(actually, embedding algorithms) allow us to represent $\bar{\F}_p$
without using any special polynomial. %

The isomorphism problem was first investigated by
Lenstra~\cite{LenstraJr91}, who showed that it can be solved in
deterministic polynomial time. %
A thorough review of all known algorithms is given in the paper
``Computing Isomorphisms and Embeddings of Finite Fields'', written
with L.~Brieulle, J.~Doliskani, J.-P.~Flori and
É.~Schost~\cite{brieulle2018computing}, and included in the
appendix. %
In the paper, we study the more general \emph{embedding problem} of
two finite fields $k⊂K$. %

\begin{problem}[Embedding description]
  Given two finite fields $k=\F_p[X]/f(X)$ and $K=\F_p[Y]/g(Y)$, with
  $\deg f$ dividing $\deg g$, determine elements $α∈k$ and $β∈K$ such
  that $k=\F_p(α)$, and such that there exists an embedding $ϕ$
  mapping $α$ to $β$.
\end{problem}

It is easily seen that $(α,β)$ describes an embedding if and only if
$α$ and $β$ share the same minimal polynomial. %
Therefore, the simplest solution, although not the most efficient,
consists in taking the class of $X$ for $α$, and a root of $f(X)$ in
$K$ for $β$. %

Given an embedding description $(α,β)$, the associated embedding (and
its partial inverse) can be evaluated on any element of $k$ by linear
algebra. %
More efficient techniques, similar to those employed in the previous
section for composita, are also available. %
They are not discussed in the appendix, but they are described in the
extended version~\cite{ffisom-long} of~\cite{brieulle2018computing}. %

The algorithms for embedding description are very similar to those to
compute irreducible polynomials. %
For simplicity, we shall only discuss here isomorphisms, i.e.,
$k≃K$. %
We refer to the appendix for the general problem. %

There essentially exist two big families: the ``Kummer family'', a
generalization of the ``Kummer case'' for primary towers discussed in
Section~\ref{sec:spec-famil-irred}; and the ``Cyclotomic family'', a
generalization of the Adleman--Lenstra algorithm. %
Each of these families can come in a ``genus 0'' flavor, like the
Kummer case for primary towers, or in a ``genus 1'' flavor, like the
Couveignes--Lercier construction.%
\footnote{Note that higher genus generalization are possible, but they
  seldom give efficient algorithms.} %
In Table~\ref{tab:ffalgos} we summarize the known constructions for
computing irreducible polynomials and isomorphism descriptions,
according to these categories. %


\begin{table}
  \centering
  \small
  \begin{tabular}{l | c | c}
    & Irreducible polynomials
    & Isomorphisms\\
    \hline
    Kummer $g=0$
    & Shoup~\cite{Shoup_1990,shoup93,shoup94}
    & Lenstra~\cite{LenstraJr91},
      Allombert~\cite{Allombert02}\\
    %%
    Kummer $g=1$
    & Couveignes--Lercier~\cite{couveignes+lercier11}
    & Narayanan~\cite{narayanan2016fast}\\
    %%
    Cyclotomic $g=0$
    & Adleman--Lenstra~\cite{Adleman-Lenstra}
    & Pinch~\cite{Pinch}, Rains~\cite{rains2008}\\
    %% 
    Cyclotomic $g=1$
    & ---
    & Pinch~\cite{Pinch}, BDDFS~\cite{brieulle2018computing}
  \end{tabular}
  \caption{Main algorithmic ideas to compute irreducible polynomials
    and isomorphisms of finite fields, by inventors.}
  \label{tab:ffalgos}
\end{table}

We will now describe Kummer-type algorithms first, then
cyclotomic-type. %
The common principle for all of them is to compute a special element,
say in $\F_{p^n}$, uniquely defined up to automorphisms of
$\F_{p^n}$. %

\paragraph{Lenstra--Allombert algorithm.}
In~\cite{LenstraJr91}, Lenstra proved that the isomorphism problem can
be solved in deterministic polynomial time, without focusing much on
getting the best possible complexity. %
In~\cite{Allombert02,Allombert02-rev}, Allombert modified Lenstra's algorithm to
obtain an efficient one; in doing so, he replaced some routines with
polynomial factorization, thus dropping determinism. %
In~\cite{brieulle2018computing}, we give several variants of
Allombert's algorithm that are more efficient, both asymptotically and
in practice. %
Allombert has included in PARI/GP both his variants and ours. %

The Lenstra--Allombert algorithm is similar in spirit to Shoup's
algorithm for computing irreducible
polynomials~\cite{Shoup_1990,shoup93,shoup94}. %
Let $k,K$ be two isomorphic copies of $\F_{p^n}$, the idea is to
choose $α∈k$ and $β∈K$ to be solutions to Hilbert's theorem 90: these
are not uniquely defined up to automorphisms, but at least they are
unique \emph{up to a scalar}. %

Assume, for example, that $n$ divides $p-1$, and fix a $n$-th root of
unity $ζ_n∈\F_p$. %
An element $α∈k$ is a solution to Hilbert 90 if and only if
$α^p=ζ_nα$; it is immediate to see that any other solution is of the
form $cα$ for $c∈\F_p$. %
Hence, if $β∈K$ is also a solution to Hilbert 90, any isomorphic image
of $β$ in $k$ is such that $α/β=c∈\F_p$; the problem is then to find
this scalar. %

Lenstra and Allombert differ in the way the scalar $c$ is found. %
We describe here Allombert's variant:
\begin{enumerate}
\item Compute a $n$-th root of unity $ζ_n∈\F_p$;
\item Find solutions $α∈k$ and $β∈K$ to Hilbert 90 relative to $ζ_n$;
\item Compute $a=α^n$ and $b=β^n$, they are both in $\F_p$;
\item Compute $c=\sqrt[n]{a/b}∈\F_p$ using a polynomial factoring
  algorithm;
\item Return $α$ and $cβ$.
\end{enumerate}

To extend the algorithm to arbitrary $n$, assume first that $p$ does
not divide $n$. %
Like in Shoup's algorithm, we adjoin the necessary roots of unity to
the base fields: Allombert factors the $n$-th cyclotomic polynomials
$Φ_n$ and extends scalars to $A_n=\F_p(ζ_n)$, whereas Lenstra uses the
unfactored polynomial and constructs the ring $A_n=\F_p[Z]/Φ_n(Z)$. %
Then, the same algorithm as above is run in $\F_{p^n}⊗A_n$, and the
result is descended to $\F_{p^n}$ using a projection. %
Note that, in both cases, $\F_{p^n}⊗A_n$ is not necessarily a field. %

Finally, extensions of degree $p^k$ are dealt with an \emph{additive
  variant} of the algorithm above, analogous to Shoup's construction
based on Artin--Schreier theory. %
Then, a solution for a generic $n=p^kn'$ is obtained by combining
(either by multiplying or by adding) the multiplicative solution for
$n'$ and the additive one for $p^k$. %

The dominant cost in the Lenstra--Allombert algorithm is computing the
solution to Hilbert 90. %
In general, $\F_{p^n}⊗A_n$ is an algebra of degree $O(n^2)$, thus
there is no hope to obtain an algorithm better than quadratic. %
In~\cite{brieulle2018computing} we show that it is indeed possible to
achieve the optimum, and even lower than that in favorable cases. %

\begin{proposition}[{Brieulle, D., Doliskani, Flori, Schost~\cite{brieulle2018computing}}]
  \def\MM{\mathsf{M}} %
  Let $k,K$ be two extensions of degree $r$ over $\F_p$, where $r$ is
  a prime power. %
  Let $s$ be the order of $p$ in $(ℤ/rℤ)^×$. %
  Let $ω$ be an exponent such that $n×n$ matrices with coefficients in
  $\F_p$ can be multiplied using $n^ω$ operations, and let $\MM(n)$ be
  the cost of multiplying polynomials of degree at most $n$ in
  $\F_p[X]$. %
  Allombert's algorithm computes its output using on average
  \begin{itemize}
  \item $O(s^{(\omega-1)/2}r^{(\omega+1)/2}\log(r)+\MM(r)\log(p))$
    operations if $s \in O(r^{(\omega-3)/(\omega-5)})$, or
   \item
     $O(
     r^{(\omega^2-4\omega-1)/(\omega-5)}+(s+r^{2/(5-\omega)})\MM(r)\log(p)
     +s^{\omega-1}r\log(r)\log(s))$ operations if
     $s \in \Omega(r^{(\omega-3)/(\omega-5)})$ and
     $s \in O(r^{1/(\omega-1)})$, or
  \item $O(\MM(r^2)\log^2(r) + \MM(r)\log(r)\log(p))$ operations
    otherwise.
  \end{itemize}
\end{proposition}

Note that the bounds for the first two cases could be improved using
algorithms of Kedlaya and Umans~\cite{KeUm11}, however we do not
consider these algorithms as they are deemed unpractical.

An elliptic curve variant of the Lenstra--Allombert algorithm was
recently proposed by Narayanan~\cite{narayanan2016fast}. %
Historically, it is the first isomorphism algorithm to
achieve a quasi-quadratic complexity, however it is deeply dependent
on Kedlaya and Umans' results, thus unlikely to be practical. %


\paragraph{Rains' algorithm.}
Rains' algorithm is an improvement over an idea of
Pinch~\cite{Pinch}. %
Rains never published his findings, however his algorithm was
eventually implemented in Magma v2.14. %
The original paper is still unpublished, the only publicly available
sources for it being, at the moment, Magma's source code%
\footnote{Precisely, in file \texttt{package/Ring/FldFin/embed.m}.}, %
and our paper~\cite{brieulle2018computing}. %
An elliptic curve generalization of the algorithm was also originally
proposed by Pinch, and then improved in~\cite{brieulle2018computing}
using ideas similar to Rains'. %

The key idea is similar to the Adleman--Lenstra algorithm. %
If $k,K$ are two isomorphic copies of $\F_{p^n}$, find an integer $ℓ$
such that $\F_{p^n}≃\F_p(ζ_ℓ)$, where $ζ_ℓ$ is an $ℓ$-th root of
unity; then the roots of the cyclotomic polynomial $Φ_ℓ$ generate both
$k$ and $K$ over $\F_p$. %
However, the roots of $Φ_ℓ$ are only uniquely defined (up to
isomorphism) if $Φ_ℓ$ is irreducible over $\F_p$, i.e., if $n=φ(ℓ)$. %
In order to uniquely define an element of $k,K$ in general, Rains suggested
using \emph{Gaussian periods}, i.e., traces of roots of unity in a
number field. %

\begin{definition}[Gaussian period]
  Let $p$ be a prime, and let $ℓ$ be a squarefree integer such that
  $(ℤ/ℓℤ)^× = 〈p〉 × S$ for some $S$.  %
  For any primitive $ℓ$-th root of unity $ζ_ℓ$ in $\bar{\F}_p$, define
  the Gaussian period $η_p(ζ_ℓ)$ as
  \begin{equation*}
    η_p(ζ_ℓ) = \sum_{σ∈S}{ζ_ℓ^{σ}}.
  \end{equation*}
\end{definition}

It is a classic fact that the periods $η(ζ_ℓ)$, as $ζ_ℓ$ runs through
the roots of $Φ_ℓ$, form a normal basis of $\F_p(ζ_ℓ)$; thus $η(ζ_ℓ)$
is uniquely defined up to isomorphism. %
Rains' algorithm follows immediately:
\begin{enumerate}
\item Find a \emph{small} $ℓ$ such that $(ℤ/ℓℤ)^×=〈p〉×S$, with
  $\#〈p〉=n$;
\item Take random roots of unity $ζ_ℓ∈k$ and $ζ_ℓ'∈K$;
\item Return the Gaussian periods $α=η(ζ_ℓ)$ and $β=η(ζ_ℓ')$.
\end{enumerate}

However it may happen that no such \emph{small} $ℓ$ exists. %
Rains' solution to the problem (identical to Adleman and Lenstra's) is
to extend scalars to a small degree auxiliary extension
$\F_q=\F_{p^s}$, with $s∧n=1$, and apply the same algorithm to
$k⊗\F_q$ and $K⊗\F_q$; then the result is descended to an isomorphism
of $k,K$ by taking a trace. %

A different way to solve the problem is to generalize Gaussian periods
to \emph{elliptic periods}. %
Let $E/\F_p$ be an elliptic curve, and suppose that $π|E[ℓ]$ acts like
a matrix $\mat{λ&0\\0&μ}$; suppose that the order in $(ℤ/ℓℤ)^×$ of,
say, $λ$ is equal to $n$, then the eigenspace of $λ$ is contained in
$E(\F_{p^n})$. %
By mimicking the definition of Gaussian periods, we can obtain a
uniquely defined element of $\F_{p^n}$. %

\begin{definition}[Elliptic period]
  Let $E/\F_p$ be an elliptic curve of $j$-invariant not $0$ or
  $1728$. %
  Let $ℓ > 3$ be an Elkies prime for $E$, $λ$ an eigenvalue
  of $π$, and $P$ a point of order $ℓ$ such that $π(P)=λP$. %
  Suppose that there is a subgroup $S$ of $(ℤ/ℓℤ)^×$ such
  that
  \begin{equation*}
    (ℤ/ℓℤ)^× = 〈λ〉 × S.
  \end{equation*}
  
  Then we define an \emph{elliptic period} as
  \begin{equation*}
    η_{λ,S}(P) =
    \begin{cases}
      \sum_{σ∈S/\{±1\}} {x \left([σ] P \right)} & \text{if $-1∈S$,}\\
      \sum_{σ∈S} {x \left([σ] P \right)} & \text{otherwise,}
    \end{cases}
  \end{equation*}
  where $x(P)$ denotes the abscissa of $P$.
\end{definition}

It is immediate to modify Rains' algorithm to use elliptic periods
instead of Gaussian ones, the freedom in the choice of the curve
$E/\F_p$ enabling us to find a smaller $ℓ$ without the need for an
auxiliary extension. %
However, we encounter a problem: elliptic periods do not form normal
bases, in general. %
While it is easy to find examples where elliptic periods are not
normal, it is enough for our purposes that they generate $\F_{p^n}$ as
a field. %
Heuristically, this is an extremely likely event, hence, in principle,
our elliptic variant of Rains' algorithm has a very tiny failure
probability; more detailed statements are given in
Section~\ref{ffisom:sec:rains-elliptic}.

However, when we tried to find example inputs on which the elliptic
variant fails, we were surprised to find none, despite an extensive
search over more than 43 million curves, carefully documented
in~\cite{ffisom-long}. %
Our failed search has thus led us to state the conjecture below, that
elliptic period always generate their field of definition, implying
that the elliptic variant of Rains algorithm never fails.

\begin{conjecture}[{Brieulle, D., Doliskani, Flori,
    Schost~\cite{brieulle2018computing}}]
  Let $E/\F_p$ be an elliptic curve with $j$-invariant not $0$ or
  $1728$; let $ℓ$ be an Elkies prime for $E$, and $P∈E[ℓ]$ a point in
  the eigenspace of a Frobenius eigenvalue $λ$ for $ℓ$. %
  Assume that $(ℤ/ℓℤ)^× = 〈λ〉 × S$, then the elliptic period
  $\eta_{\lambda,S}(P)$ generates $\F_p(x(P))$ over $\F_p$.
\end{conjecture}

The complexity of Rains' algorithm is extremely sensitive to how small
the integer $ℓ$ is. %
Unfortunately, even assuming the generalized Riemann hypothesis,
bounds on $ℓ$ are very loose, thus provable bounds on the complexity
of the algorithm are very bad. %
However, in practice we expect that $ℓ=O(n\log n)$, and we give enough
experimental evidence in~\cite{brieulle2018computing} to support this
heuristic. %
Assuming this heuristic bound, we can prove that Rains' algorithm runs
in average time $\tildO(n^{(ω+1)/2}+n\log q)$, where $ω$ is the
\emph{exponent of linear algebra}, while the elliptic variant runs in
time $\tildO(n^2\log q)$. %

These bounds are remarkable: according to them, Rains' original
algorithm is the only isomorphism algorithm with subquadratic
complexity. %
However this bound is only heuristic, and experiments show that, both
the original algorithm and the elliptic variant, perform faster than
Allombert's algorithm only in very limited cases. %



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

\section{Lattices of finite fields}

We end this chapter coming back to the problem of representing the
algebraic closure $\bar{\F}_p$. %
We saw how special families of polynomials can be used to represent
finite extensions of $\F_p$ in a \emph{compatible},
\emph{incremental}, and possibly \emph{unique} way, and thus can also
be used to represent the whole $\bar{\F}_p$. %
At the opposite end of the spectrum we have the possibility of
representing finite extensions of $\F_p$ by arbitrary polynomials, and
provide compatibility through a general purpose embedding algorithm
such as those presented in the previous section. %

This approach was first formalized by Bosma, Cannon and Steel, in
``Lattices of Compatibly Embedded Finite
Fields''~\cite{bosma+cannon+steel97}. %
They implemented it as the default system for Magma; to compute
embeddings, they originally used the naive approach based on
polynomial factoring, then added Rains' algorithm as an alternative. %
To this day, Magma still has the most efficient system to represent
lattices of arbitrary extensions of $\F_p$. %

The Bosma--Cannon--Steel framework maintains a single data structure:
a collection (a lattice) of compatible extension fields. %
We may add new extensions to the lattice, at the user's request, by
computing embeddings into each of the fields already present in it,
and storing the embedding data along. %

However, a naive implementation of this idea may easily get stuck. %
Take for example $p=5$, and a lattice containing $\F_{p^2}$,
$\F_{p^4}$ and $\F_{p^6}$; assume that the extensions are defined by
the polynomials in the diagram below. %
\begin{equation*}
  \begin{tikzpicture}
    \draw
    (0,-1) node (F0) {$\F_5$}
    (0,0) node(Fp) {$\F_5[X]/(X^2-X+2)$}
    (-1,1) node[anchor=east](Fpm) {$\F_5[X]/(X^4-X^2+2)$}
    (1,1) node[anchor=west](Fpn) {$\F_5[X]/(X^6-X^3+2)$}
    (0,2) node(Fpmn) {$\F_5[X]/(X^{12}-X^6+2)$};
    \draw
    (Fp) edge (Fpm) edge (Fpn) edge (F0)
    (Fpmn) edge (Fpm) edge (Fpn);
  \end{tikzpicture}
\end{equation*}
Denote by $η_2,η_4,η_6$ the classes of $X$ in
$\F_{p^2},\F_{p^4},\F_{p^6}$ respectively, and assume that we have
chosen the embeddings $η_2↦η_4^2$ and $η_2↦η_6^3$. %
Now, suppose that we want to add $\F_{p^{12}}$ to the lattice. %
We start by embedding $\F_{p^4}\hookrightarrow\F_{p^{12}}$ with
$η_4↦η_{12}^{15}$; at this point, we are not anymore free to choose
any embedding for $\F_{p^6}\hookrightarrow\F_{p^{12}}$: indeed,
choosing $η_6↦η_{12}^2$ would imply $η_{12}^{6}=η_2=η_{12}^{30}$, and
thus $η_{12}^{24}=1$, which is impossible because all 24th roots of
unity are in $\F_{5^2}$. %

The \emph{tour de force} by Bosma, Cannon and Steel consists in
showing that it is always possible to construct compatible lattices,
if one does so carefully. %
They define six conditions that the lattice must satisfy in order to
ensure compatibility; we paraphrase them below:
\begin{description}
\item[\emph{Uniqueness:}] For every pair of fields $k,K$ in the lattice,
  there is at most one embedding $k\hookrightarrow K$.
\item[\emph{Reflexivity:}] Every field is embedded in itself through
  the identity morphism.
\item[\emph{Prime subfield:}] $\F_p$ is embedded in every field via the
  canonical embedding.
\item[\emph{Invertibility:}] If $k≃K$, then the embeddings
  $k\hookrightarrow K$ and $K\hookrightarrow k$ are inverse to one
  another.
\item[\emph{Transitivity:}] For any triple $k⊂K⊂L$ the embeddings
  $ϕ_{k,K}:k→K$, $ϕ_{K,L}:K→L$, $ϕ_{k,L}:k→L$, are compatible, i.e.,
  $ϕ_{k,L}=ϕ_{K,L}∘ϕ_{k,K}$.
\item[\emph{Intersection:}] For any triple $k,K,L$ such that $k⊂L$ and
  $K⊂L$, the subfield $k∩K$ is also in the lattice and is compatibly
  embedded in $k,K,L$.
\end{description}

By maintaining these properties throughout a session, Magma is able to
ensure compatibility regardless of the number of finite fields created
by the user. %
If a criticism must be addressed to this data structure, it is on the
combinatorial explosion that it entails: for any field in the lattice,
the data on embeddings to any other subfield must be stored, thus
storage grows quadratically in the number of fields in the lattice. %
Also, as more and more fields are added, more and more computations
must be performed to keep compatibility. %
Nevertheless, Magma has still today undoubtedly the most efficient
system to represent the algebraic closure of a finite field. %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

\section{Perspectives}

Despite 40 years of research, the question of computing in extensions
of $\F_p$ is not closed yet: there is still progress to be made both
on the practical and the theoretical side. %

\paragraph{Implementations.}
As we have seen, the only computer algebra systems implementing a
generic mechanism to compute in $\bar{\F}_p$ are Magma and SageMath. %
Neither can be said to be really efficient, but the prize for the
fastest and most feature-rich undoubtedly goes to Magma. %

The spectrum of available algorithms is nowadays considerably larger
than what is used in these two systems, and it would be worth
experimenting with them with the goal of beating the current
implementations. %

With H.~Randriam, É.~Rousseau and É.~Schost, we have started
experimenting with the Bosma--Cannon--Steel framework in the new
computer algebra system Nemo~\cite{Fieker:2017:NCA:3087604.3087611}. %
A reproduction of the system in Magma has already been implemented by
É.~Rousseau\footnote{\url{https://github.com/erou/LatticesGF.jl}}, and
we are now exploring possible ways to improve its efficiency. %

Unfortunately, no single catch-all technique emerges from the theory,
thus experiments will necessarily have to take many different
techniques into account. %

After having obtained convincing results, it will be highly desirable
to port the techniques that worked best to SageMath. %
This will be facilitated by the fact that Nemo and SageMath share the
same low-level C library in Flint, which is where we are adding the
critical parts of the algorithms we test. %

\paragraph{Special families.}
Special families of irreducible polynomials are the most promising
option for efficiently representing $\bar{\F}_p$, and the only one
granting uniqueness. %
However, at the moment they have serious drawbacks that make them an
unrealistic target for implementation. %
For one, they are quite complex to implement: the Couveignes--Lercier
construction, for example, requires algorithms for counting points of
elliptic curves.%
\footnote{Realistically, though, a naive algorithm is enough, given
  that the Couveignes--Lercier algorithm is only practical for
  relatively small base fields.} %
Finally, when the base field gets relatively large, the
Couveignes--Lercier construction becomes too costly, and must be
replaced by Shoup's construction, which is not quasi-optimal. %
Thus, a first goal would be to find a simple algorithm for
constructing primary towers, that is reasonably efficient for any
parameter. %

Even with a good construction for primary towers, we then need to
construct composita in order to deal with general extensions. %
Our construction is reasonably simple and efficient, however it is not
optimal when it comes to vector space isomorphisms, and thus it is not
optimal for $\bar{\F}_p$ either. %
A construction for composita with quasi-linear complexity would be a
big discovery, and would likely pave the way for a larger adoption of
special families. %
In the meantime, our construction is by far the one with the best
available complexity, and is simple enough that it would be worth
experimenting with it. %

A radically different approach would be to keep the decomposition of
$\bar{\F}_p$ as a tensor product of primary towers, i.e., to represent
elements as multivariate polynomials modulo an ideal of univariate
polynomials. %
We have already said that known techniques, e.g., Kronecker
substitution, incur an exponential penalty in the number of variables,
i.e., the number of primary factors. %
Improving this complexity would be a major breakthrough in computer
algebra, with consequences that reach well beyond implementing
$\bar{\F}_p$.

\paragraph{On uniqueness and elegance.}
Uniqueness in families of polynomials is an interesting question,
because there is a social aspect to it. %

Unfortunately, there is no ``natural'' choice for a unique family of
irreducible polynomials. %
What come closest to a canonical definition of an algebraic closure of
a finite field is Conway's construction of the field $\mathbf{On}_2$,
which contains $\bar{\F}_2$ as a subfield~\cite{Conway:ONAG2000}. %
However, as Lenstra showed~\cite{LENSTRA1977389}, computing the finite
subfields of $\mathbf{On}_2$ is not trivial. %
Furthermore, no satisfactory generalization of Conway's work is known
for general $p$. %

Thus even reasonably simple proposals, such as Conway polynomials
(which are mostly unrelated to $\mathbf{On}_2$), require a certain
dose of \emph{ad hocness}, such as a ``lexicographically
constraint''. %

Any algorithm for computing irreducible polynomials can be
artificially turned into a deterministic one by fixing random
choices. %
However, the main motivation for uniqueness is data portability: i.e.,
the possibility to run the same computation in two computer algebra
system (two different systems, the same system but different sessions,
or versions, ...), and obtain the same results. %
Thus, for a unique construction of irreducible polynomials to be
accepted, it must be simple enough that all systems can implement it
correctly, test it easily, and it must also be popular enough that
all systems \emph{want to} implement it. %

I am afraid that the Couveignes--Lercier construction does not fit the
bill. %
Shoup's construction would be acceptable, but as long as its
advantages over Conway polynomials are not clearly visible, I suspect
few developers will be willing to implement it. %

Therefore, I am convinced that a simple enough construction, even if
not optimal, offering advantages similar to Conway polynomials at a
lesser cost, would be extremely valuable to the community. %

\paragraph{Isomorphisms.}
I am sure that the hole in Table~\ref{tab:ffalgos} has not gone
unnoticed. %
Before the reader jumps on filling it, let me tell that I do not see
how to obtain an interesting algorithm from it. %

One obvious idea would be to look for curves $E/\F_p$ with a certain
number of points, construct some isogeny of degree $ℓ$, and use its
kernel polynomial to define an irreducible polynomial of the wanted
degree (maybe using elliptic periods?). %
However, this approach would not have a better complexity than the
Adleman--Lenstra algorithm, in the same way that the elliptic variant
of Rains' algorithm does not have a better complexity than the original
one. %
It would also quite probably require the use of the $ℓ$-th modular
polynomial, since the computations involved are very similar to those
for the \nameref{prob:expl-isog} we saw in the previous chapter; thus
it would probably also be unpractical. %

A different approach would use curves defined over number fields. %
This is probably even more desperate, given how hard it is to find
torsion points on them. %

Coming to something concrete, now, the obvious breakthrough would be
to find an isomorphism algorithm with subquadratic complexity. %
Rains' algorithm comes close to it, however it requires heuristic
hypotheses that are probably out of reach. %

Less ambitiously, we may look for practical algorithms. %
Our experiments show that (one of the variants of) Allombert's
algorithm is by far the most practical of all; beating its performance
using a different paradigm would be a nice challenge. %


\paragraph{Arbitrary extensions.}
Moving to lattices of arbitrary extensions, we have already discussed
the combinatorial explosion that the Bosma--Cannon--Steel data
structure suffers from. %
I am currently interested in taking ideas from isomorphism algorithms,
and applying them to lattices of extensions, in the hope of reducing
the amount of information that needs to be stored. %

More in detail, we have seen that all isomorphism algorithms are based
on the principle of finding some ``(almost) uniquely defined''
generators for the finite fields. %
We may imagine more than this: we may hope to find a \emph{lattice of
  uniquely defined generators} such that generators are ``compatible''
in some way. %
This would allow storing only the generators, one per field, and
deduce all embeddings from them. %

The analogy between isomorphism algorithms and algorithms for
irreducible polynomials, shown in Table~\ref{tab:ffalgos}, also hints
at the fact that these \emph{lattices of generators} would be a sort
of ``half-way'' construction, between special families of polynomials
and arbitrary lattices, and may potentially lead to new solutions to
the uniqueness problem mentioned above.

Limited examples of this idea are easy to produce: think for example
of the lattice of roots of unity, defining the ``cyclotomic
extensions'' of $\F_p$. %
However finding a general construction capable of describing arbitrary
extensions seems harder. %
We are currently exploring this idea in conjunction with the
Lenstra--Allombert algorithm, and hope to have interesting results
soon. %


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapart{art/train-color}
\chapter{Telemetry}
\label{cha:crypto}

In Chapter~\ref{cha:tate} we learned how to classify isogenies over
finite fields. %
For ordinary curves, we defined the depth of $E/\F_q$ as the valuation
of the conductor $[\O_K:\End(E)]$ at some prime $ℓ$. %
We saw how to effectively compute the depth, and how to recognize
ascending, descending, and horizontal isogenies. %
The structure theorems revealed that there are three possible shapes
of $ℓ$-isogeny graphs, only differing in the structure of the surface:
a single curve in the Atkin case, a pair of curves in the ramified
case, and a \emph{crater} (a cycle) in the Elkies case. %

However, we left two questions unanswered: for a given curve $E/\F_q$
and a prime $ℓ$, how many vertices does its $ℓ$-isogeny graph
contain? %
And, for a given quadratic imaginary field $ℚ(π)$ and a prime $ℓ$, how
many distinct $ℓ$-isogeny graphs are there?

The first question is easy to answer for the Atkin and the ramified
case: we know indeed that isogeny volcanoes have height
$h=v_ℓ(\sqrt{Δ_π/Δ_K})$, therefore an Atkin volcano contains
$((ℓ+1)^{h+1}-1)/ℓ$ curves, whereas a ramified volcano contains
$2(ℓ+1)^h$ curves. %
In order to determine the size of the crater in the Elkies case, and
to answer the second question, we will have to resort to the theory of
\emph{complex multiplication}. %
We will then learn that, while heights tend to be ``small'' (i.e.,
logarithmic in $q$), craters tend to be ``large'' (polynomial in $q$). %

At this point, we will begin studying large isogeny graphs containing
isogenies of mixed degree. %
We will be faced with a new problem that is finding a ``short''
isogeny path between two curves in a graph, and upon this problem we
will build a new cryptographic primitive. %
We will then turn our attention to supersingular isogeny graphs. %
The unique properties of the Frobenius endomorphism of supersingular
curves will allow us to build a much more efficient cryptographic
primitive, known by the name of CSIDH. %
Finally, by pushing the study of supersingular graphs further, we will
get to the primitive known as SIDH, the building block of
SIKE~\cite{SIKE}, one of the candidates to the NIST call for
post-quantum public key encryption~\cite{NIST2016}. %


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

\section{Complex multiplication}
\label{sec:compl-mult}

Let $\O$ be an order in a quadratic imaginary field $K=ℚ(\sqrt{-D})$,
we say that an elliptic curve $E$ has \emph{complex multiplication by
  $\O$} (or, in short, \emph{CM} by $\O$) if $\End(E)≃\O$. %
We have already seen that all ordinary elliptic curves over finite
fields have complex multiplication, with $K=ℚ(π)$. %

Supersingular curves have the similar property
$\End_{\F_q}(E)≃\O⊂ℚ(\sqrt{-q})$, whenever $q$ is an odd power of
a prime $p>3$. %
Strictly speaking, no supersingular curve should be said to have
complex multiplication, because the ring of endomorphisms defined over
the algebraic closure is larger (more on this later); we will
nevertheless use the name for this special case.

We now present a group action on the set of all curves having complex
multiplication by a fixed order $\O$. %
We will denote by $\Ell_q(\O)$ the set of isomorphism classes over
$\bar{\F}_q$ of curves with complex multiplication by $\O$,
and we will assume that it is non-empty. %

Let $\a$ be an invertible ideal in $\End(E)≃\O$, of norm coprime to
$q$, and define the \emph{${\a}$-torsion} subgroup of $E$ as
\begin{equation*}
  \label{eq:a-torsion}
  E[\a] = \{P ∈ E(\bar{\F}_q) \mid σ(P) = 0
  \text{ for all } σ ∈ \a \}.
\end{equation*}
This subgroup is the kernel of a separable isogeny
$\phi_{\a}:E→E/E[\a]$; it can be proven that $\phi_{\a}$ is
horizontal, and that its degree is the \emph{norm} of $\a$. %
By composing with an appropriate purely inseparable isogeny, the
definition of $ϕ_\a$ is easily extended to invertible ideals of any
norm.

Writing $\a·E$ for the isomorphism class of the image of $ϕ_\a$, we
get an action $·:\mathcal{I}(\O)×\Ell_q(\O)→\Ell_q(\O)$ of the group
of invertible ideals of $\O$ on $\Ell_q(\O)$. %
It is then apparent that endomorphisms of $E$ correspond to principal
ideals in $\O$, and act trivially on $\Ell_q(\O)$. %
Recall that the \emph{class group} $\Cl(O)$ is defined as the quotient
of $\mathcal{I}(\O)$ by the subgroup $\mathcal{P}(\O)$ of principal
ideals; since the above action factors through $\mathcal{P}(\O)$, it
natural to consider the induced action of $\Cl(\O)$ on $\Ell_q(\O)$. %
The main theorem of complex multiplication states that this action is
\emph{simply transitive}. %

\begin{theorem}[Complex multiplication]
  Let $\F_q$ be a finite field, $\O⊂ℚ(\sqrt{-D})$ an order in a
  quadratic imaginary field, and $\Ell_q(\O)$ the set of
  $\bar{\F}_q$-isomorphism classes of curves with complex
  multiplication by $\O$. %

  Assume $\Ell_q(\O)$ is non-empty, then it is a \emph{principal
    homogeneous space} for the class group $\Cl(\O)$, under the action
  \begin{align*}
    \Cl(\O) × \Ell_q(\O) &→ \Ell_q(\O),\\
    (\a,E)  &↦ \a·E
  \end{align*}
  defined above.
\end{theorem}

Being a principal homogeneous space means that, for any fixed base
point $E∈\Ell_q(\O)$, there is a bijection
\[
\begin{aligned}
\Cl(\O) &\longrightarrow \Ell_q(\O) \\
\text{Ideal class of }\a &\longmapsto \text{Isomorphism class of }\a\cdot E.
\end{aligned}
\]
Recall that $\Cl(\O)$ is abelian and finite, and that its order is
called the \emph{class number} of $\O$, and denoted by $h(\O)$. %
We have just proven that $\#\Ell_q(\O)=h(\O)$, and we also have
answered both questions we had asked at the beginning of the chapter.

\begin{corollary}
  Let $\O$ be a quadratic imaginary order, and assume that
  $\Ell_q(\O)$ is non-empty. %
  Let $ℓ$ be a prime such that $\O$ is $ℓ$-maximal, i.e., such that
  $ℓ$ does not divide the conductor of $\O$. %
  All $ℓ$-isogeny volcanoes of curves in $\Ell_q(\O)$ are
  isomorphic. %
  Furthermore, one of the following is true.
  \begin{enumerate}
  \item[(0)] If the ideal $(ℓ)$ is prime in $\O$, then there are
    $h(\O)$ distinct $ℓ$-isogeny volcanoes of Atkin type, with surface
    in $\Ell_q(\O)$.
  \item[(1)] If $(ℓ)$ is ramified in $\O$, i.e., if it decomposes as a
    square $\frak l^2$, then there are $h(\O)/2$ distinct $ℓ$-isogeny
    volcanoes of ramified type, with surface in $\Ell_q(\O)$.
  \item[(2)] If $(ℓ)$ splits as a product $\frak l·\hat{\frak l}$ of
    two distinct prime ideals, then there are $h(\O)/n$ distinct
    $ℓ$-isogeny volcanoes of Elkies type, with craters in $\Ell_q(\O)$
    of size $n$, where $n$ is the order of $\frak l$ in $\Cl(\O)$.
  \end{enumerate}
\end{corollary}

Like in Chapter~\ref{cha:tate}, we are mostly interested in Elkies
volcanoes. %
We already saw that if $π|T_ℓ(E)$ diagonalizes as $\mat{λ&0\\0&μ}$
with $λ≠μ$, to each eigenvalue we can associate a direction on the
crater of the $ℓ$-volcano. %
The same phenomenon can be observed through complex multiplication:
associate to $λ$ and $μ$ the prime ideals $\a=(π-λ,ℓ)$ and
$\hat{\a}=(π-μ,ℓ)$, both of norm $ℓ$; then $E[\a]$ is the eigenspace
of $λ$, and $E[\hat{\a}]$ that of $μ$. %
Because $\a\hat{\a} = \hat{\a}\a = (ℓ)$, the ideal classes $\a$ and
$\hat{\a}$ are the inverse of one another in $\Cl(\O)$, therefore the
isogenies $ϕ_{\a}:E→\a·E$ and $ϕ_{\hat{\a}}:\a·E→E$ are dual to one
another (up to isomorphism). %

We see, once again, that the eigenvalues $λ$ and $μ$ define two
opposite directions on the $\ell$-isogeny crater, independent of the
starting curve, as shown in Figure~\ref{fig:cycle}. %
The size of the crater is the order of $(π-λ,ℓ)$ in $\Cl(\O)$, and the
set $\Ell_q(\O)$ is partitioned into craters of equal size.

\begin{figure}[t]
  \begin{minipage}{0.45\textwidth}
    \centering
    \begin{tikzpicture}
      \def\crater{7}
      \foreach \i in {1,...,\crater} {
        \begin{scope}[shorten >=0.1cm,->]
          \draw[blue!60!black] (360/\crater*\i : 1.95cm) -- (360/\crater*\i+360/\crater : 1.95cm);
          \draw[blue!60!white] (360/\crater*\i+360/\crater : 2.05cm) -- (360/\crater*\i : 2.05cm);
        \end{scope}
        \draw[blue!60!black] (360/\crater*\i+180/\crater:1.6cm) node {\small$λ$};
        \draw[blue!60!white] (360/\crater*\i+180/\crater:2cm) node {\small$μ$};
      }
      \foreach \i in {1,...,\crater} {
        \draw[fill] (360/\crater*\i:2cm) circle (2pt);
      }
    \end{tikzpicture}
    \caption{An isogeny cycle for an Elkies prime $ℓ$, with edge directions
      associated with the Frobenius eigenvalues $λ$ and $μ$.}
    \label{fig:cycle}
  \end{minipage}
  \hfill
  \begin{minipage}{0.45\textwidth}
    \centering
    \begin{tikzpicture}
      \def\crater{12}
      \def\jumpa{-8}
      \def\jumpb{9}
      \def\diam{2cm}

      \foreach \i in {1,...,\crater} {
        \draw[blue] (360/\crater*\i : \diam) to[bend right] (360/\crater*\i+360/\crater : \diam);
        \draw[red] (360/\crater*\i : \diam) to[bend right] (360/\crater*\i+\jumpa*360/\crater : \diam);
        \draw[green] (360/\crater*\i : \diam) to[bend right=50] (360/\crater*\i+\jumpb*360/\crater : \diam);
      }
      \foreach \i in {1,...,\crater} {
        \pgfmathparse{int(mod(2^\i,13))}
        \let\exp\pgfmathresult
        \draw[fill] (360/\crater*\i: \diam) circle (2pt);% +(360/\crater*\i: 0.4) node{$x^{\exp}$};
      }
    \end{tikzpicture}
    \caption{Graph of horizontal isogenies on 12 curves, with isogenies
      of three different degrees (represented in different colors).}
    \label{fig:cayley}
  \end{minipage}
\end{figure}

For the rest of the chapter, we will focus mostly on craters of
isogeny volcanoes, with horizontal isogenies. %
In some cases, we will also assume that volcanoes have height 0, so
that the crater is the whole graph; for obvious reasons, these are
also called \emph{isogeny cycles} in the
literature~\cite{couveignes+morain94}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

\section{Quaternion algebras}

Supersingular curves are generally not covered
by the theory of complex multiplication. %
For most of them, indeed, the Frobenius endomorphism acts like an element of
$ℤ$, instead of acting like a ``complex multiplier''. %

Supersingular curves are defined by the fact that multiplication by
$p$ is purely inseparable, i.e., $E[p]$ is trivial. %
This implies that the curve $E^{(p^2)}$ is isomorphic to $E$, and thus
that both are isomorphic to a curve defined over $\F_{p^2}$. %

If $E/\F_{p^2}$ is a supersingular curve, its Frobenius endomorphism
must satisfy $π^2-tπ+p^2=0$, with $t$ a multiple of $p$; hence, by
Hasse's theorem, $t∈\{0,±p,±2p\}$. %
The cases $t∈\{0,±p\}$ only happen for a very limited number of curves
with $j$-invariant $0$ or $1728$; we are thus mostly interested in the
case $t=±2p$, i.e., $π=±p$. %
In this case, $π|T_ℓ(E)$ acts like a scalar matrix for any $ℓ≠p$,
hence, by \hyperref[th:tate]{Tate's theorem}, $\End(E)⊗ℚ_ℓ$ is
isomorphic to the full space of $2×2$ matrices over $ℚ_ℓ$. %
With a little more work, we can prove that $\End(E)⊗ℚ$ is isomorphic
to the quaternion algebra $B_{p,∞}$ ramified at $p$ and at infinity. %

With more effort, we can prove that $\End(E)$ is isomorphic to a
\emph{maximal} order $\O⊂B_{p,∞}$. %
Like the CM case, isogenies are in correspondence with (left) ideals
of $\O$. %
Unlike the CM case, $B_{p,∞}$ has more than one maximal order, and
there is no concept of \emph{depth}, thus no ascending, descending or
horizontal isogenies. %

More precisely, let $\a⊂Β_{p,∞}$ a lattice, the \emph{left order} of $\a$ is
the ring $\O(\a)=\{x∈B_{p,∞}\mid x\a⊂\a\}$. %
Two lattices $\a,\frak b$ are said to be \emph{right isomorphic} if
$\a=\frak b x$ for some $x∈B_{p,∞}$. %
If $\O⊂B_{p,∞}$ is an order, $\a$ is called a \emph{left ideal} of $\O$ if
$\O⊂\O(\a)$; the \emph{left class set} $\Cl(\O)$ is the set of right
ideal classes of left ideals of $\O$. %
The order $\#\Cl(\O)$ only depends on the quaternion algebra, and is
called the \emph{class number} of $B_{p,∞}$. %
Analogous definitions can be given by swapping left and right; we
refer to~\cite[Chapter~42]{Voight2018} for more properties and
definitions. %

Like in the CM case, the set $\Cl(\O)$ is in bijection with the vertex
set of a supersingular graph. %

\begin{theorem}
  Let $B_{p,∞}$ be the quaternion algebra ramified at $p$ and
  infinity, and let $\O⊂B_{p,∞}$ be a maximal order. %
  Let $E_0/F_{p^2}$ be a supersingular elliptic curve with
  $\End(E_0)≃\O$. %
  \begin{enumerate}
  \item The number of isomorphism classes of supersingular elliptic
    curves is equal to the class number of $B_{p,∞}$.
  \item There is a one-to-one correspondence $\a↦\a·E_0$ between
    $\Cl(\O)$ and the set of isomorphism classes of supersingular
    elliptic curves, such that $\End(\a·E_0)$ is isomorphic to the
    right order of $\a$.
  \end{enumerate}
\end{theorem}

This theorem can be turned into an equivalence of categories,
see~\cite[Theorem~45]{kohel}. %
Thanks to the Eichler mass formula, we obtain the exact size of the
isogeny class. %

\begin{corollary}
  The number of isomorphism classes of supersingular elliptic curves
  is equal to
  \begin{equation*}
    \left\lfloor\frac{p}{12}\right\rfloor +
    \begin{cases}
      0 &\text{if $p=1\mod 12$,}\\
      1 &\text{if $p=5,7\mod 12$,}\\
      2 &\text{if $p=11\mod 12$.}
    \end{cases}
  \end{equation*}
\end{corollary}

We thus have a bound on the size of a supersingular isogeny graph over
$\F_{p^2}$. %
Since the Frobenius acts like a scalar, all isogenies are defined over
$\F_{p^2}$, hence supersingular $ℓ$-isogeny graphs are necessarily
$(ℓ+1)$-regular. %
In the next section we will learn that the supersingular $ℓ$-isogeny
graph has a unique connected component. %


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Expander graphs from isogenies}

We are now going to introduce new families of isogeny graphs suitable
for cryptographic use. %
We will want them to somehow ``behave like large random graphs'',
while at the same time having a strong algebraic structure: the first
is needed for security, the second to produce complex protocols such
as key exchange. %

The random-like properties of isogeny graphs are typically expressed
in terms of \emph{expansion}. %
An undirected graph on $n$ vertices has $n$ real eigenvalues
$λ_1≥\cdots≥λ_n$, and, if the graph is $k$-regular, it can be proven
that $k=λ_1≥λ_n≥-k$. %
Because of this equality, $λ_1$ is called the \emph{trivial
  eigenvalue}. %
An \emph{expander graph} is a $k$-regular graph such that its
non-trivial eigenvalues are bounded away, in absolute value, from
$k$. %
We recall here some basic facts about expanders; for an in depth
review, see~\cite{Goldreich2011,tao2011expander}.

\begin{definition}[Expander graph]
  Let $ε>0$ and $k≥1$. A $k$-regular graph is called a (one-sided)
  \emph{$ε$-expander} if
  \[λ_2≤(1-ε)k;\]
  and a \emph{two-sided $ε$-expander} if it also satisfies
  \[λ_n≥-(1-ε)k.\] %
  A sequence $G_i=(V_i,E_i)$ of $k$-regular graphs with $\#V_i→∞$ is
  said to be a one-sided (resp. two-sided) \emph{expander family} if
  there is an $ε>0$ such that $G_i$ is a one-sided (resp. two-sided)
  $ε$-expander for all sufficiently large $i$.
\end{definition}

\begin{theorem}[Ramanujan graph]
  Let $k≥1$, and let $G_i$ be a sequence of $k$-regular graphs. %
  Then
  \[\max(|λ_2|,|λ_n|) ≥ 2\sqrt{k-1} - o(1),\]
  as $n→∞$. %
  A graph such that $|λ_j|≤2\sqrt{k-1}$ for any $λ_j$ except $λ_1$ is
  called a \emph{Ramanujan graph}.
\end{theorem}

Two related properties of expander graphs are relevant to us. %
First, they have \emph{short diameter}: as $n→∞$ the diameter of an
expander is bounded by $O(\log n)$, with the constant depending only
on $k$ and $ε$. %
Second, expanders have \emph{rapidly mixing walks}: loosely speaking,
the next proposition says that random walks of length close to the
diameter terminate on any vertex with probability close to uniform. %

\begin{proposition}[Mixing theorem~(\cite{jao+miller+venkatesan09})]
  Let $G=(V,E)$ be a $k$-regular two-sided $ε$-expander. %
  Let $F⊂V$ be any subset of the vertices of $G$, and let $v$ be any
  vertex in $V$. %
  Then a random walk of length at least
  \[\frac{\log(\#F^{1/2}/(2\#V))}{\log(1-ε)}\] %
  starting from $v$ will land in $F$ with probability at least
  $\#F/(2\#V)$.
\end{proposition}

The walk length in the mixing theorem is also called the \emph{mixing
  length} of the expander graph. %

Random regular graphs typically make good expanders, but only a
handful of deterministic constructions is known, most of them based on
Cayley graphs~\cite{LubPS,chung1989diameters,Goldreich2011}. %

\begin{definition}[Cayley graph]
  Let $G$ be a group and $S⊂G$ be a symmetric subset (i.e., $s∈S$
  implies $s^{-1}∈S$). %
  The \emph{Cayley graph} of $(G,S)$ is the undirected graph whose
  vertices are the elements of $G$, and such that there is an edge
  between $g$ and $sg$ if and only if $s∈S$. %
\end{definition}

In our case, we will construct a Cayley graph by ``gluing many isogeny
cycles together'': we take $\Ell_q(\O)$ as vertex set, select a subset
of ideals $S⊂\Cl(\O)$ represented by isogenies of bounded prime
degree, and draw an edge between $E$ and $\a·E$ for any $\a∈S$. %
This graph is called the \emph{Schreier graph} of
$(\Cl(\O),S,\Ell_q(\O))$, and is isomorphic to the Cayley graph of
$(\Cl(\O),S)$; an example is shown in Figure~\ref{fig:cayley}. %

\begin{theorem}[{Jao, Miller, Venkatesan~\cite{jao+miller+venkatesan09}}]
  \label{th:ord-exp}
  Let $\O$ be a quadratic imaginary order, and assume that
  $\Ell_q(\O)$ is non-empty. %
  Let $δ>0$, and define the graph $G$ on $\Ell_q(\O)$ where two
  vertices are connected whenever there is a horizontal isogeny
  between them of prime degree bounded by $O((\log q)^{2+δ})$.

  Then $G$ is a regular graph and, under the generalized Riemann
  hypothesis for the characters of $\Cl(\O)$, there exists an $ε$
  independent of $\O$ and $q$ such that $G$ is a two-sided
  $ε$-expander.
\end{theorem}

The theorem is readily generalized to supersingular
curves and isogenies defined over $\F_p$. %

A radically different construction of expander graphs is given by
graphs of supersingular curves \emph{defined over $\F_{p^2}$} with
$ℓ$-isogenies, for a \emph{single} prime $ℓ≠p$. %
Two examples of such graphs are shown in
Figure~\ref{fig:sup-97-2-3}. %
This construction is related to LPS
graphs~\cite{LubPS,Lub,cryptoeprint:2018:593}, but is not isomorphic
to a Cayley graph. %

\begin{theorem}[{Mestre~\cite{mestre86}, Pizer~\cite{pizer1,pizer2}}]
  \label{th:ss-exp}
  Let $\ell≠p$ be two primes. %
  The $ℓ$-isogeny graph of supersingular curves in $\bar\F_p$, is
  connected, $(ℓ+1)$-regular, and has the Ramanujan property.
\end{theorem}

\begin{figure}
  \centering
  \begin{tikzpicture}
    \def\graph{
      \begin{scope}[every node/.style={fill,black,circle,inner sep=2pt}]
        \node at (0,0)  (1){};
        \node at (0,4) (20){};
        \node at (2,1)  (16z){};
        \node at (-2,1)  (81z){};
        \node at (-1,2) (77z){};
        \node at (1,2)  (20z){};
        \node at (-2,3)  (85z){};
        \node at (2,3)  (12z){};
      \end{scope}
    }
    
    \graph
    \begin{scope}[blue,every loop/.style={looseness=50}]
      \path (1) edge (20) edge (16z) edge (81z);
      \path (20) edge[loop left] (20) edge[loop right] (20);
      \path (16z) edge (81z) edge (77z);
      \path (81z) edge (20z);
      \path (77z) edge (20z) edge (85z);
      \path (20z) edge (12z);
      \path (12z) edge[bend right=10] (85z) edge[bend left=10] (85z);
    \end{scope}
        
    \begin{scope}[xshift=6cm]
      \graph
      \begin{scope}[red]
        \path (1) edge (85z) edge (81z) edge (12z) edge (16z);
        \path (20) edge (85z) edge (77z) edge (20z) edge (12z);
        \path (81z) edge (85z) edge (77z) edge (16z);
        \path (85z) edge (12z);
        \path (12z) edge (16z);
        \path (16z) edge (20z);
        \path (20z) edge[bend right=10] (77z) edge[bend left=10] (77z);
      \end{scope}
    \end{scope}
  \end{tikzpicture}
  \caption{Supersingular isogeny graphs of degree 2 (left, blue) and 3
    (right, red) on $\F_{97^2}$.}
  \label{fig:sup-97-2-3}
\end{figure}


Both of these isogeny graphs will be used in the next sections to
build key exchange protocols. %
For reasons that will be apparent soon, there will only be a mild
connection between the expansions properties of the graphs and the
security of the protocols: the expansion theorems will mostly serve as
a blueprint for devising good cryptosystems, but will have no provable
impact. %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

\section{Key exchange from CM graphs}

The first isogeny-based protocol was introduced by Couveignes during a
talk at the École Normale Superieure in 1997, although it was only
published ten years later in~\cite{cryptoeprint:2006:291};
independently, Rostovtsev and Stolbunov proposed similar protocols
in~\cite{rostovtsev+stolbunov06,Stol}. %
Couveignes' key exchange protocol was presented in a more general
setting, applying to any principal homogeneous space satisfying some
cryptographic properties.

Recall that a principal homogeneous space (PHS) for a group $G$ is a
set $X$ with an action of $G$ on $X$ such that for any $x,x'\in X$,
there is a unique $g\in G$ such that $g\cdot x = x'$. %
Equivalently, the map $φ_x: g\mapsto g\cdot x$ is a bijection between
$G$ and $X$ for any $x\in X$. %
Couveignes defines a \emph{hard homogeneous space} (HHS) to be a PHS
where the action of $G$ on $X$ is efficiently computable, but
inverting the isomorphism $φ_x$ is computationally hard for any~$x$.

Any HHS $X$ for an abelian group $G$ can be used to construct a key
exchange based on the hardness of inverting $\varphi_x$: the system
parameters are a HHS $(G,X)$, and a starting point $x_0∈X$; a secret
key is a random element $g∈G$, and the associated public key is
$g·x_0$. %
If Alice and Bob have keypairs $(g_A,x_A)$ and $(g_B,x_B)$,
respectively, then the commutativity of $G$ lets them derive a shared
secret
\begin{equation*}
  g_A·x_B = g_A·g_B· x_0 = g_B·g_A·x_0 = g_B·x_A.
\end{equation*}
The analogy with classic group-based Diffie--Hellman is evident.

Couveignes suggested to use $\Ell_q(\O)$ as an instance of a HHS: the
system parameters are a starting curve $E/\F_q$, and the associated
class group $\Cl(\O)$; the secret keys are random elements of
$\Cl(\O)$, and public keys are $j$-invariants of curves in
$\Ell_q(\O)$. %
However, given a generic element of $\Cl(\O)$, the best
algorithm~\cite{jao+soukharev10} to evaluate its action on
$\Ell_q(\O)$ has subexponential complexity in $q$, making the protocol
infeasible. %

Instead, following Rostovtsev and
Stolbunov~\cite{rostovtsev+stolbunov06}, we may choose to represent
elements of $\Cl(\O)$ in a way that makes it easy to evaluate the
group action. %
We fix a set $S$ of ideals in $\Cl(\O)$ of small degree, possibly in
such a way that the associated Cayley graph is an expander. %
Instead of sampling uniformly random elements of $\Cl(\O)$, we sample
random walks in the Schreier graph of $(\Cl(\O),S,\Ell_q(\O))$. %
The walks can be computed efficiently as a composition of small degree
isogenies, and, if they are long enough, they approach the uniform
distribution on $\Ell_q(\O)$. %
The protocol is illustrated in Figure~\ref{fig:dh-walk-pict}. %


\begin{figure}
  \centering
  \newcommand{\myedge}[3]{
    \draw[#3] (360/\crater*#1 : \diam) to[bend right] (360/\crater*#2 : \diam);
  }
  \begin{tikzpicture}
    \begin{scope}
      \def\crater{12}
      \def\jumpa{-8}
      \def\jumpb{9}
      \def\diam{2cm}
      \foreach \i in {1,...,\crater} {
        \pgfmathparse{int(mod(2^\i,13))}
        \let\exp\pgfmathresult
        \draw[fill] (360/\crater*\i: \diam) circle (2pt);
      }
      % Alice 1
      \myedge{0}{1}{blue}\myedge{1}{5}{red}\myedge{5}{6}{blue}\myedge{6}{3}{green}
      % Bob 2
      \begin{scope}[dashed,thick]
        \myedge{3}{7}{red}\myedge{7}{11}{red}\myedge{11}{8}{green}\myedge{8}{9}{blue}
      \end{scope}
      \draw (0 : \diam + 0.4cm) node {$E_0$};
      \draw (360/\crater*3 : \diam + 0.4cm) node {$E_A$};
      \draw (360/\crater*9 : \diam + 0.4cm) node {$E_{AB}$};
    \end{scope}
    
    \begin{scope}[xshift=6.5cm]
      \def\crater{12}
      \def\jumpa{-8}
      \def\jumpb{9}
      \def\diam{2cm}
      \foreach \i in {1,...,\crater} {
        \pgfmathparse{int(mod(2^\i,13))}
        \let\exp\pgfmathresult
        \draw[fill] (360/\crater*\i: \diam) circle (2pt);
      }
      % Bob 1
      \begin{scope}[dashed,thick]
        \myedge{0}{4}{red}\myedge{4}{8}{red}\myedge{8}{5}{green}\myedge{5}{6}{blue}
      \end{scope}
      % Alice 2
      \myedge{6}{7}{blue}\myedge{7}{11}{red}\myedge{11}{0}{blue}\myedge{0}{9}{green}
      \draw (0 : \diam + 0.4cm) node {$E_0$};
      \draw (360/\crater*6 : \diam + 0.4cm) node {$E_B$};
      \draw (360/\crater*9 : \diam + 0.4cm) node {$E_{AB}$};
    \end{scope}
  \end{tikzpicture}  

  \caption{Example of key exchange on the isogeny graph of
    Figure~\ref{fig:cayley}. %
    Alice's path is represented by continuous lines, Bob's path by
    dashed lines. %
    On the left, Bob computes the shared secret starting from Alice's
    public data. %
    On the right, Alice does the analogous computation.}
  \label{fig:dh-walk-pict}
\end{figure}


\paragraph{Towards a practical key exchange.}
Even with these adjustments, the protocol is far from practical:
Stolbunov managed to run a 108 bit secure implementation in around 5
minutes~\cite{Stolbunov2012}. %
To understand why, let's see how a random element of $\Cl(\O)$ is
sampled and the group action evaluated. %
We have a set $S$ of prime ideals of $\O$, represented as $(π-λ,ℓ)$
for some eigenvalue $λ$ modulo a prime $ℓ$. %
A secret key corresponds to a product of ideals in $S$:
\begin{equation}
  \label{eq:iso-walk}
  \frak s = \prod_{\a_i∈S}\a_i^{e_i}.
\end{equation}
For simplicity, we may assume that the exponents $e_i$ are taken in a
box $[-B,B]$,%
\footnote{Negative values represent the dual direction to $(π-λ,ℓ)$,
  associated to the ideal $(π-μ,ℓ)$.} %
then the size of the key space is at most $(2B+1)^{\#S}$. %

On the other hand, evaluating the action of $\frak s$ requires
computing at most $\#S·B$ isogenies. %
We see that, for a fixed set $S$, increasing $B$ only increases the
key space polynomially, while it also increases the running time
linearly. %
On the other hand, for a fixed $B$, increasing $\#S$ exponentially
increases the key space, while it only increases the running time
linearly. %
Thus, to strike a balance between security and running time, we need
to use a fairly large set $S$: values in the hundreds are typical for
$\#S$, and all ideals in $S$ must have different (prime) norms to
avoid duplicates. %
Hence, evaluating the action of $\frak s$ implies computing up to
$\#S·B$ isogenies of degrees as large as a few thousands! %

What algorithms do we have at our disposal to compute these
isogenies? %
We have a curve $E$, a prime $ℓ$ and a \emph{direction} $π-λ$. %
Without further assumptions, we have an instance of the
\nameref{prob:expl-isog}: we want to enumerate the isogenies of degree
$ℓ$, and choose the one that is horizontal of direction $π-λ$. %
We are thus stuck with Elkies' or Couveignes' algorithm, both
requiring to evaluate and factor the modular polynomial $Φ_ℓ$ in the
first place. %
It is no surprise then that evaluating one $\Cl(\O)$-action takes
several minutes. %

Is it possible to do better? %
One idea that comes to mind is to use Vélu's formulas instead. %
This idea was explored in ``Towards practical key exchange from
ordinary isogeny graphs'', written with J.~Kieffer and
B.~Smith~\cite{10.1007/978-3-030-03332-3_14}, and included in the appendix to
this document. %
Suppose, for example, that $π|E[ℓ]$ acts like $\mat{1&0\\0&μ}$, with
$μ≠1$. %
In this case, there is an easily recognizable direction associated to
the eigenvalue $1$: the corresponding eigenspace is the cyclic group
of rational $ℓ$-torsion points. %
A point in this eigenspace can be computed by taking a random point in
$E(\F_q)$, and multiplying it by $\#E/ℓ$: there is a $(ℓ-1)/ℓ$ chance
that the result is not zero, and can thus be used to compute the
$ℓ$-isogeny of direction $π-1$ using Vélu's formulas. %

We can do even better. %
Suppose that $π|E[ℓ]$ acts like $\mat{1&0\\0&-1}$, then both
directions are recognizable: $π-1$ is obtained like before, while
$π+1$ corresponds to the rational $ℓ$-torsion subgroup of a
\emph{quadratic twist}%
\footnote{A \emph{quadratic twist} is a curve isomorphic to $E$ over
  $\F_{q^2}$, hence it represents the same point in the isogeny
  graph.} %
of $E$. %
More generally, we can use primes such that $π|E[ℓ]$ acts like
$\mat{-λ&0\\0&λ^{-1}}$: then, if $r$ is the order of $λ\pmod{ℓ}$, one
direction is identified with the rational $ℓ$-torsion subgroup of
$E(\F_{q^r})$, and the other one with that of a quadratic twist. %
If $r$ is not too large, this approach is still faster than using
Elkies' algorithm.

At any rate, the constraints we are putting on $π$ force three
conditions:
\begin{enumerate}
\item $q=-1 \mod ℓ$,
\item $\leg{Δ_π}{ℓ}=1$,
\item the roots of $π^2-tπ+q\mod ℓ$ have small multiplicative order,
\end{enumerate}
and this for each of the primes $ℓ$ we want to include in the set $S$.

The first condition is easy to fulfill: choose a prime
$q=f·\prod_i ℓ_i - 1$ for some cofactor $f$. %
The other two are much harder, because they essentially require
finding a curve $E/\F_q$ with a specific trace $t$. %
The best technique at our disposal consists in taking random curves
$E/\F_q$ and computing $\#E$, until a suitable one is found. %

In~\cite{10.1007/978-3-030-03332-3_14} we go at great length optimizing the
search for a good curve, using \emph{modular curves} and an
\emph{early abort} variation on the SEA point counting algorithm. %
Despite all our efforts, the search is still extremely hard, and the
best curve we could find in 17,000 CPU-hours satisfies the constraints
above for only 12 primes, plus relaxed constraints for 11 other
primes. %

The final result is still disappointing: a 128-bit secure key exchange
that runs in about 5 minutes.


\paragraph{CSIDH.}
Somehow, we have not been bold enough. %
What if we asked even more stringent constraints? %

For example, we may ask that $π|E[ℓ]=\mat{1&0\\0&-1}$ for all primes
in $S$. %
This forces the trace $t$ of $π$ to be $0\pmod{ℓ}$. %
If we impose this constraint for enough primes, because of Hasse's
theorem, we actually force it for \emph{every} prime. %
Thus we end up with a trace zero supersingular curve. %

We may be tempted\footnote{As I was.} to quickly dismiss this case,
because supersingular curves do not have complex multiplication. %
However, as already mentioned in Section~\ref{sec:compl-mult}, Delfs
and Galbraith~\cite{Delfs2016} showed that if we restrict to curves,
endomorphisms and isogenies defined over a prime field $\F_p$, we have
a perfect clone of the ordinary complex multiplication case. %
Indeed, if $E$ is a supersingular curve defined over a prime field
$\F_p$ with $p>3$, it has trace zero and its endomorphism ring is isomorphic to
either $ℤ[\sqrt{-p}]$ or $ℤ[(1+\sqrt{-p})/2]$. %
For such a curve, every prime $ℓ$ such that $\leg{-4p}{ℓ}=1$ is an Elkies
prime, with eigenvalues equal to $±\sqrt{-p}$.

In~\cite{10.1007/978-3-030-03332-3_15}, Castryck, Lange, Martindale, Panny
and Renes introduce CSIDH\footnote{Pronounced ``sea-side''.}: a variant
of the Couveignes--Rostovtsev--Stolbunov system where all isogenies
can be computed using Vélu's formulas. %
CSIDH uses a prime $p$ of the form $4·\prod_iℓ_i-1$, and a
supersingular curve $E/\F_p$ as starting point, so that
$π|E[ℓ_i]=\mat{1&0\\0&-1}$ for all $ℓ_i$. %
By cleverly optimizing computations, they achieve a key-exchange at
the 128 bits security level in only 0.1 seconds. %

Now, I would love to add~\cite{10.1007/978-3-030-03332-3_15} to the appendix,
but it seems that the rules do not allow me to. %
I strongly encourage the reader to look for the paper online and read
it for themselves. %

In the next section we are going to present another key exchange
protocol based on supersingular isogeny graphs. %
The graph structure will be radically different, but Vélu's formulas
will still play a crucial role for its performance.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Key exchange from supersingular graphs}

In the previous section we saw how supersingular curves allowed us to
go from a dramatically slow protocol to a fairly efficient one. %
The upshot is the following: we can control the group structure of
supersingular curves simply by controlling the order of the base field
$\F_q$; this lets us choose curves with many rational points of small
order, which in turn can be used to construct small degree isogenies
via Vélu's formulas. %
Ultimately, specially crafted supersingular curves let us navigate
their isogeny graph very efficiently. %

Can we apply the same principle to the Ramanujan graphs of
Theorem~\ref{th:ss-exp}? %
This is the idea behind the two papers ``Towards Quantum-Resistant
Cryptosystems from Supersingular Elliptic Curve Isogenies'', written
with D.~Jao and J.~Plût~\cite{jao+defeo2011,defeo+jao+plut12}, the
second of which is included in the appendix. %
In this section we will briefly describe the ideas behind this
protocol, that has come to be known as SIDH\footnote{An acronym for
  Supersingular Isogeny Diffie Hellman}.

SIDH uses supersingular curves $E/\F_{p^2}$ with trace $±2p$, for a
specially chosen $p$.%
\footnote{Note that this case includes trace zero curves $E/\F_p$,
  after extending scalars to $\F_{p^2}$.} %
For these curves $π|E[ℓ]=±\mat{p&0\\0&p}$ for any $ℓ≠p$, and there
are exactly $ℓ+1$ isogenies of degree $ℓ$. %

Compared to the complex multiplication case, graphs of supersingular
isogenies have two attractive features. %
First, one isogeny degree is enough to obtain an expander graph: this
allows us to use isogenies of a single small prime degree, e.g., $2$
or $3$, instead of many small prime degrees up to the thousands. %
Second, there is no action of an abelian group, such as $\Cl(\O)$, on
them: we will see in the next section how this thwarts attacks by
quantum computers.

The key idea of SIDH is to let Alice and Bob take random walks in two
distinct $ℓ$-isogeny graphs on the same vertex set of all
supersingular $j$-invariants defined over $\F_{p^2}$. %
We will denote by $ℓ_A$ and $ℓ_B$ the isogeny degrees used by Alice
and Bob respectively. %
Figure~\ref{fig:sup-97-2-3} shows a toy example of such graphs, where
$p=97$, $ℓ_A=2$ and $ℓ_B=3$. %

Like in CSIDH, we want to be able to evaluate $ℓ$-isogenies using
Vélu's formulas, thus we need $p=±1\pmod{ℓ}$. %
However, this is not enough to define a key exchange protocol, as we
shall see. %
Instead, we will use Vélu's formulas to evaluate an isogeny of degree
$ℓ^e$, for some large exponent $e$, all at once. %
Therefore, we select a prime of the form $p\mp 1=ℓ_A^{e_A}ℓ_B^{e_B}f$,
where $e_A$ and $e_B$ are exponents to be determined and $f$ is a
small cofactor, so that $E/\F_{p^2}$ contains the full subgroups
$E[ℓ_A^{e_A}]$ and $E[ℓ_B^{e_B}]$. %
Typical values are $p = 2^{250}3^{159}-1$ or $p = 2^{372}3^{239}-1$
(see~\cite{SIKE}). %

The protocol now proceeds similarly to the
Couveignes--Rostovtsev--Stolbunov key exchange: Alice chooses a secret
walk of length $e_A$ in the $ℓ_A$-isogeny graph; this is equivalent to
her choosing a secret cyclic subgroup $〈A〉⊂E[ℓ_A^{e_A}]$. %
Bob does the same in the $ℓ_B$-isogeny graph, choosing a secret
$〈B〉⊂E[ℓ_B^{e_B}]$. %
Then, there is a well defined subgroup $〈A〉+〈B〉=〈A,B〉$, defining
an isogeny to $E/〈A,B〉$. %
Since we have taken care to choose $ℓ_A≠ℓ_B$, the group $〈A,B〉$ is
cyclic of order $ℓ_A^{e_A}ℓ_B^{e_B}$. %
This is illustrated in Figure~\ref{fig:sidh-diag}.

\begin{figure}
  \centering
  \begin{tikzpicture}
    \begin{scope}
      \draw (0,1.2) node[anchor=east] {$\bl{\ker α=〈A〉}⊂ E[\ell_A^{e_A}]$};
      \draw (0,0.4) node[anchor=east] {$\rd{\ker β=〈B〉}⊂ E[\ell_B^{e_B}]$};
      \draw (0,-0.4) node[anchor=east] {$\ker α' = 〈\rd{β}\bl{(A)}〉$};
      \draw (0,-1.2) node[anchor=east] {$\ker β' = 〈\bl{α}\rd{(B)}〉$};
    \end{scope}
    \begin{scope}[xshift=4.5cm]
      \large
      \node[matrix of nodes, ampersand replacement=\&, column sep=3cm, row sep=1.5cm] (diagram) {
        |(E)| $E$ \& |(Es)| $E/〈\bl{A}〉$ \\
        |(Ep)| {$E/〈\rd{B}〉$} \& |(Eps)| {$E/〈\bl{A},\rd{B}〉$}\\
      };
      \path[->,blue] (E) edge node[auto] {$α$} (Es);
      \path[->] (Ep) edge node[auto,swap] {$α'$} (Eps);
      \path[->,red] (E) edge node[auto,swap] {$β$} (Ep);
      \path[->] (Es) edge node[auto] {$β'$} (Eps);
    \end{scope}
  \end{tikzpicture}
  \caption{Commutative isogeny diagram constructed from Alice's and
    Bob's secrets. %
    Quantities known to Alice are drawn in blue, those known to Bob
    are drawn in red.}
  \label{fig:sidh-diag}
\end{figure}

After Alice and Bob have computed their respective secrets $〈A〉$ and
$〈B〉$, we need them to exchange enough information to both compute
$E/〈A,B〉$ (up to isomorphism). %
However, publishing $E/〈A〉$ and $E/〈B〉$ does not give enough
information to the other party, and the diagram in
Figure~\ref{fig:sidh-diag} shows no way by which they could compute
$E/〈A,B〉$ without revealing their secrets. %

We solve this problem by a very peculiar trick, which sets SIDH apart
from other isogeny based protocols. %
The idea is to let Alice and Bob publish some additional information
to help each other compute the shared secret. %
Let us summarize what are the quantities known to Alice and Bob. %
To set up the cryptosystem, they have publicly agreed on a prime $p$
and a supersingular curve $E$ such that
\[E(\F_{p^2}) ≃ (ℤ/ℓ_A^{e_A}ℤ)^2⊕(ℤ/ℓ_B^{e_B}ℤ)^2⊕(ℤ/fℤ)^2.\] %
It will be convenient to also fix public bases of their respective
torsion groups:
\begin{align*}
  E[ℓ_A^{e_A}] &= 〈P_A,Q_A〉,\\
  E[ℓ_B^{e_B}] &= 〈P_B,Q_B〉.
\end{align*}
To start the protocol, they choose random secret subgroups
\begin{align*}
  〈A〉 &= 〈[m_A]P_A+[n_A]Q_A〉 ⊂ E[ℓ_A^{e_A}],\\  
  〈B〉 &= 〈[m_B]P_B+[n_B]Q_B〉 ⊂ E[ℓ_B^{e_B}],
\end{align*}
of respective orders $ℓ_A^{e_A},ℓ_B^{e_B}$, and compute the secret
isogenies
\begin{align*}
  α : E &\to E/〈Α〉,\\
  β : E &\to E/〈B〉.
\end{align*}
They respectively publish $E_A=E/〈Α〉$ and $E_B=E/〈B〉$. %

Now, to compute the shared secret $E/〈A,B〉$, Alice needs to compute
the isogeny $α':E/〈B〉\to E/〈A,B〉$, whose kernel is generated by
$β(A)$. %
We see that the kernel of $α'$ depends on both secrets, thus Alice
cannot compute it without Bob's assistance. %
The trick here is for Bob to publish the values $β(P_A)$ and $β(Q_A)$:
they do not require the knowledge of Alice's secret, and we will
assume that they do not give any advantage in computing $E/〈A,B〉$ to
an attacker. %
From Bob's published values, Alice can compute $β(A)$ as
$[m_A]β(P_A) + [n_A]β(Q_A)$, and complete the protocol. %
Bob performs the analogous computation, with the help of Alice. %
The protocol is schematized in Figure~\ref{fig:sidh}.

\begin{figure}
  \centering
  \begin{tikzpicture}
    \node[matrix of nodes, ampersand replacement=\&, column sep=4mm, row sep=2cm] (diagram) {
      \& |(1)| $E$ \\
      |(a)| \parbox{1.5cm}{$E/〈\bl{A}〉$\\{\footnotesize $\bl{α}(P_B)\\\bl{α}(Q_B)$}} \& \&
      |(b)| \parbox{1.5cm}{$E/〈\rd{B}〉$\\{\footnotesize $\rd{β}(P_A)\\\rd{β}(Q_A)$}}\\
      \normalsize $\frac{E/〈\bl{A}〉}{\rd{α(B)}} \simeq$ \&
      |(ab)|  $E/〈\bl{A},\rd{B}〉$ \&
      \normalsize $\simeq \frac{E/〈\rd{B}〉}{\bl{β(A)}}$\\
    };
    \small
    \path[blue] (1) edge node[auto,swap](phia) {$α$} (a);
    \path[red] (1) edge node[auto](phib) {$β$} (b);
    \path[red] (a) edge node[auto,swap](psia){$β'$} (ab);
    \path[blue] (b) edge node[auto](psib){$α'$} (ab);
    \path[dashed,->] (phia) edge node[auto]{\footnotesize $\rd{α(B)}$} (psia);
    \path[dashed,->] (phib) edge node[auto,swap]{\footnotesize $\bl{β(A)}$} (psib);
  \end{tikzpicture}

  \caption{Schematics of SIDH key exchange. Quantities only known to
    Alice are drawn in blue, quantities only known to Bob in red.}
  \label{fig:sidh}
\end{figure}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Security and quantum computers}

We end this chapter with a quick review of the security of the key
exchange protocols presented so far. %
The problem that is often cited as the cornerstone of isogeny based
cryptography is the \emph{isogeny walk problem}.

\begin{problem}[Isogeny walk problem]
  \label{prob:iwp}
  Let $\F_q$ be a finite field. %
  Given two elliptic curves $E,E'$ defined over $\F_q$ such that
  $\#E(\F_q)=\#E'(\F_q)$, find an isogeny $E→E'$ of smooth degree.
\end{problem}

The ``smooth degree'' requirement is there so that the isogeny can be
represented compactly as a composition of small degree isogenies. %
We are purposefully vague on the distribution where $E,E'$ are taken
from, because this is going to depend on the cryptosystem. %
Naturally, the first parameter to look at is the size of the isogeny
class of $E,E'$: too small, and we can find the isogeny by brute
force. %

\paragraph{Security of CM constructions.}
In the CM case, using the \emph{bathymeter} developed in
Chapter~\ref{cha:tate}, we can find ascending paths from $E$ and $E'$
to two curves $\hat{E},\hat{E}'$ with complex multiplication by the
maximal order; then, we are left with the problem of finding a
horizontal isogeny between $\hat{E}$ and $\hat{E'}$. %
Since the horizontal isogeny class of $\O_K$ is the smallest among all
horizontal isogeny classes of curves with complex multiplication by
some $\O⊂\O_K$, it makes sense to reduce to this case, as first noted
by Galbraith, Hess and Smart~\cite{GHS,galbraith+stolbunov11}. %

\begin{problem}[Horizontal isogeny walk problem]
  \label{prob:hiwp}
  Let $\F_q$ be a finite field, and let $\O_K$ be the ring of integers
  of a quadratic imaginary field $K=ℚ(\sqrt{-D})$. %
  Given two elliptic curves $E,E'$ defined over $\F_q$ with complex
  multiplication by $\O_K$, find an isogeny $E→E'$ of smooth degree.
\end{problem}

The size of the horizontal isogeny class is $h(\O_K)$; it is known by
the class number formula that this is in $O(\sqrt{Δ_K}\log Δ_K)$, and, for the
typical isogeny class\footnote{Including the isogeny class of trace
  zero supersingular curves used in CSIDH.}, $Δ_K=O(q)$. %
The best generic attack against the \nameref{prob:hiwp} is a
Pollard-rho style algorithm, performing random walks from $E$ and $E'$
until a collision is found~\cite{GHS}. %
Its average complexity is $O(\sqrt{h(\O_K)})$, thus $O(q^{1/4})$ for a
typical isogeny class. %
This justifies choosing a prime $q$ of $4n$ bits, for a security level
of $2^n$, and this is indeed what we do
in~\cite{10.1007/978-3-030-03332-3_14} and what CSIDH
does~\cite{10.1007/978-3-030-03332-3_15}.

However, we must also ensure that the key space covers the whole
$\Ell_q(\O_K)$, possibly approaching the uniform distribution. %
This means that isogeny walks, as in Eq.~\eqref{eq:iso-walk}, must be
sampled from a relatively large subset $S⊂\Cl(\O_K)$, implying that
$\#S\gg \log q$. %
For efficiency reasons, practical instantiations take $S$ just large
enough: $\#S\sim (\log q)/2$;%
\footnote{Additional constraints in CSIDH force $\#S$ to grow as
  $(\log q)/(\loglog q)$.} %
however it will not go unnoticed that this choice is insufficient to
apply Theorem~\ref{th:ord-exp}. %
We may as well live with it, changing our security assumptions to take
into account the biased distributions given by random walks in graphs
that are not known to be expanders, as it is done
in~\cite{10.1007/978-3-030-03332-3_14}. %

\paragraph{Security of SIDH.}
Things are quite different in SIDH. %
We know that the supersingular isogeny graph over $\F_{p^2}$ has
$≈p/12$ vertices, thus in general we can find a smooth isogeny between
two supersingular curves in $O(\sqrt{p})$ operations using the same
kind of random walk algorithm. %

However, this is not the best attack against SIDH. %
To understand why, we need to look at the key space. %
Recall that the prime in SIDH is chosen of the form
$p±1=ℓ_A^{e_A}ℓ_B^{e_B}f$. %
Alice's secrets are uniformly random cyclic subgroups of
$E[ℓ_A^{e_A}]$; Alice's key space contains thus at most
$(ℓ_A+1)ℓ^{e_A-1}$ elements. %
Similarly, Bob's keyspace contains at most $(ℓ_B+1)ℓ^{e_B-1}$
elements. %
To balance out the size of the two key spaces, we need
$ℓ_A^{e_A}≈ℓ_B^{e_B}≈\sqrt{p}$. %
Thus, Alice's and Bob's key spaces only cover a tiny fraction of the
whole supersingular graph, much less they satisfy the conditions to
Theorem~\ref{th:ss-exp}. %
An isogeny path in any of the two subgraphs can be found by a
meet-in-the middle strategy (also called a \emph{claw finding}
algorithm) in only $O(p^{1/4})$ steps.%
\footnote{A Pollard-rho style of algorithm is not possible in this
  case, since its complexity would depend on the size of the whole
  graph. %
  The claw finding algorithm is very memory hungry, and some argue
  that the RAM model is not appropriate to study its complexity. %
  In a constant memory model, the currently best attack against SIDH
  is estimated to take $O(p^{3/8})$
  steps~\cite{cryptoeprint:2018:313}.} %

Hence, like in the CM setting, we need to take $\log p\sim 4n$ for a
security of $2^n$ operations. %
However SIDH $j$-invariants are elements of $\F_{p^2}$, thus they will
typically be twice as big as $j$-invariants in CSIDH. %
Adding to that the fact that SIDH public keys contain more than a
$j$-invariant (see Figure~\ref{fig:sidh}), we see that CSIDH consumes
considerably less bandwidth than SIDH. %
This is offset by the fact that SIDH is an order of magnitude faster
than CSIDH, owing to the smaller isogeny degrees. %

However, we just highlighted a very important point on SIDH: it
transmits more information than what we would normally feel
comfortable sharing. %
Indeed, SIDH transmits not only the image curve $E/〈A〉$, but also
the image of the basis points $P_B,Q_B$. %
This is enough information to interpolate the secret isogeny by a
Couveignes-like algorithm, however we do not know how to exploit the
fact that the isogeny has smooth degree, and in fact we do not know
any algorithm that takes advantage of this auxiliary information.%
\footnote{See~\cite{10.1007/978-3-319-70697-9_12} for a distant cousin
  of SIDH for which it is possible to extract useful information out
  of the auxiliary data.} %

At any rate, the security of SIDH cannot be founded on the
\nameref{prob:iwp}. %
Instead, it is necessary to make \emph{ad hoc} assumptions taking into
account the information communicated by the protocol. %
These assumptions, going under the names of CSSI, SSCDH,
SSDDH~\cite{jao+defeo2011,defeo+jao+plut12} or SIDH~\cite{SIKE}, are
too \emph{ad hoc} to deserve a space here; we refer the reader to the
appendix for their definitions.

\paragraph{Quantum security.}
The discussion on security would not be complete without surveying
quantum attacks. %
Indeed, the main selling point of isogeny-based key exchange protocols
is their (conjectured) resistance to quantum algorithms. %

Let's start with CM constructions. %
Couveignes' Hard Homogeneous Spaces setting is scarily similar to the
Diffie--Hellman key exchange, which is indeed a special case of it. %
Shor's algorithm~\cite{shor1994algorithms} solves the discrete
logarithm problem in polynomial time on a quantum computer, and thus
breaks the Diffie--Hellman protocol. %
But is there a variant of Shor's algorithm that also breaks generic
HHS constructions? %

\begin{definition}[Hidden Subgroup Problem (HSP)]
  Let $f:G→X$ be a function from a group $G$ to a set $X$. %
  Assume that there is a subgroup $H⊂G$ such that $f(g)=f(g')$ if and
  only if $g'∈gH$. %
  The function $f$ is said to \emph{hide} the subgroup $H$, and the
  \emph{hidden subgroup problem} consists in finding generators for
  $H$, given access to $f$.
\end{definition}

It is well known that Kitaev's generalization of Shor's
algorithm~\cite{kitaev1995hsp} solves the hidden subgroup problem in
quantum polynomial time, when $G$ is a finitely generated abelian
group. %

\begin{definition}[Hidden Shift Problem (HShP)]
  Let $f_0,f_1:G→X$ be two injective functions from a group $G$ to a
  set $X$. %
  Assume that there is an element $s∈G$ such that $f_0(g)=f_1(gs)$ for
  any $g∈G$. %
  The element $s$ is called a \emph{hidden shift} for $f_0,f_1$, and
  the \emph{hidden shift problem} is to find $s$, given access to
  $f_0$ and $f_1$. %
\end{definition}

For any group $G$, the hidden shift problem reduces to the hidden
subgroup problem for the (generalized) dihedral group $G\rtimes C_2$.%
\footnote{To reduce HShP to HSP, simply define the function $f$ by
  $f(g,1) = f_0(g)$ and $f(g,-1) = f_1(g)$, so that the hidden
  subgroup is generated by $(s,-1)$.} %
No generalization of Kitaev's algorithm is known for non-abelian
groups, but a different family of algorithms, due to
Kuperberg~\cite{Kup,Kuperberg2013} and Regev~\cite{regev04}, solves
the HShP in subexponential quantum time $\exp(\sqrt{\log\#G})$. %

As first noted in~\cite{childs2014constructing} and then improved
in~\cite{cryptoeprint:2018:537,BIJ18,Jao-etal-kuperberg-2018}, Kuperberg's algorithm
can be used to solve the \nameref{prob:hiwp} as follows: let $E,E'$ be
the two curves with complex multiplication by $\O_K$, define two
functions $f_0,f_1:\Cl(\O_K)\to\Ell_q(\O_K)$ as $f_0(\a)=\a·E$ and
$f_1(\a)=\a·E'$, then the hidden shift defines a horizontal isogeny
between $E$ and $E'$. %

Kuperberg's algorithm is a game changer for protocols based on complex
multiplication: indeed, to ensure $2^n$ quantum security we need to
take $\log q=O(n^2)$. %
The actual constant depends on the variant of Kuperberg's algorithm,
and various parameters such as available quantum memory; its exact
value is currently debated, but it appears that taking $\log q$
somewhere between $512$ and $1024$ bits grants a security of $2^{64}$
quantum gates~\cite{10.1007/978-3-030-03332-3_15,10.1007/978-3-030-03332-3_14,cryptoeprint:2018:537,cryptoeprint:2018:1059}.

For SIDH, on the other hand, there is no group structure%
\footnote{Outside of the subgraph of $\F_p$-rational curves, but the
  algorithm in~\cite{biasse2014quantum} does not impact the security
  of SIDH.} %
that can be exploited by Kuperberg's algorithm. %
Currently, the best quantum attack against SIDH is a Grover-like claw
finding algorithm due to Tani~\cite{tani2009claw}, requiring
$O(p^{1/6})$ quantum gates (and as many qubits!). %
For this reason, $p$ is typically chosen so that $\log p\sim 6n$ for a
quantum security of $2^n$ gates, although it is debated whether Tani's
algorithm actually presents an advantage over the classical claw
finding attack.%~\cite{todo}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Perspectives}

The field of isogeny-based cryptography is a relatively young one, and
still confidential compared to other post-quantum families. %

\paragraph{Other protocols.}
In this chapter we have only presented key exchange systems, however
it is possible to obtain other interesting protocols from isogeny
graphs. %
Public key encryption \emph{à la} El Gamal is an easy exercise,
whereas CCA-secure Key Encapsulation Methods (KEMs) already pose a
riddle. %
On one hand, key validation is problematic for SIDH, forcing the use
of generic transforms such as Fujisaki and
Okamoto's~\cite{10.1007/3-540-48405-1_34}. %
On the other hand, key validation in CM systems essentially amounts to
verifying the order of the elliptic curves; this allows CCA-secure
systems à la
DHIES~\cite{cryptoeprint:1999:007,10.1007/3-540-45353-9_12,doi:10.1137/S0097539702403773},
but also static-static non-interactive key exchange (NIKE), making
CSIDH the first practical post-quantum NIKE. %

Signatures are another soft spot of isogeny-based cryptography. %
No analogue of Schnorr signatures is known for any of the primitives
presented so far. %
Instead, we have zero-knowledge identification schemes for
SIDH~\cite{defeo+jao+plut12,10.1007/978-3-319-70972-7_9,10.1007/978-3-319-70694-8_1}
and, very recently, CSIDH~\cite{cryptoeprint:2018:824}. %
From these, we can derive signature schemes via the Fiat--Shamir
transform, but these are either slow, or have large signatures, or
both. %
It is currently an open problem to build a compact and efficient
signature scheme from isogeny primitives. %

Finally, none of the advanced protocols derived from Diffie--Helman,
such as identity based encryption, blind signatures, etc., is known to
have an isogeny-based analogue. %
One of the most advanced cryptographic ideas based on isogenies, a
sort of multilinear map, has been recently introduced by Boneh, Glass,
Krashen, Lauter, Sharif, Silverberg, Tibouchi and
Zhandry~\cite{Boneh2018}; however the idea fails to give an actual
protocol, because a key mathematical ingredient (a generalization of
the $j$-invariant of elliptic curves) is missing, and finding it was
left as an open problem by the authors.

\paragraph{Other graphs.}
It is also natural to ask whether other families of expander graphs
could be used for cryptography. %
LPS graphs~\cite{LubPS}, for example, are very much related to
supersingular graphs, and have already been proposed as a basis for
(symmetric) cryptography~\cite{charles+lauter+goren09}, although they
have been broken~\cite{tillich2008collisions,quis}. %

As another example, groupoids of maximal orders of quaternion algebras
are isomorphic to supersingular isogeny graphs; however it has been
shown that the equivalent of the~\nameref{prob:iwp} in these groupoids
can be solved in (classical) polynomial
time~\cite{kohel2014quaternion}.%
\footnote{To put this result into perspective, note that its
  equivalent for the CM case would amount to solve the discrete
  logarithm problem of $\Cl(\O)$ in classical polynomial time!} %
We do not know how to use this result to break SIDH, however it has
been employed in various security
reductions~\cite{galbraithsecurity,10.1007/978-3-319-78372-7_11}.

An obvious generalization of isogeny based protocols would consist in
replacing elliptic curves with higher dimensional varieties. %
Some advantages are to be expected: higher dimensional varieties have
larger torsion groups, thus more isogenies for a fixed degree. %
This has the potential to produce smaller parameters, however the
current knowledge on isogenies in higher dimension is still very
rudimentary, and few algorithms exist. %
Some early progress in understanding them has been made
in~\cite{lubicz_robert_2012,lubicz_robert_2015,cosset2015computing,ionica2014isogeny,Brooks2017},
it would be interesting to further develop this field. %

\paragraph{Efficiency.}
Both SIDH and CSIDH have very small keys, compared to other
post-quantum candidates (or even to RSA). %
However, SIDH is among the slowest candidates to the NIST post-quantum
competition, and CSIDH is currently an order of magnitude slower. %

Considerable efforts have been devoted to speed up SIDH, using ideas
such as \emph{optimal strategies} for Vélu's
formulas~\cite{defeo+jao+plut12}, \emph{projectivized} curve
equations~\cite{costello2016sidh}, \emph{key
  compression}~\cite{azarderakhsh2016key,Costello2017,10.1007/978-3-319-79063-3_12},
arithmetic modulo primes of special
form~\cite{costello2016sidh,vercauteren-sidh-fp,8023082}, dedicated
\emph{Montgomery ladders}~\cite{flor_sidh_x64}, and various software
and hardware level optimizations~\cite{cryptoeprint:2017:1213}. %
Owing to this, we seem to have pretty much hit a wall on how much SIDH
can be further sped up: barring spectacular discoveries%
\footnote{One particular trick in CSIDH that is completely absent in
  SIDH is using the quadratic twist to perform part of the
  computations. %
  I have thought of this for a while, and I see no fundamental reason
  why it should not work for SIDH, if it was not for the fact that
  finding suitable parameters seems computationally unfeasible. %
  My favorite example is $p=17$, so $p^2-1=2^53^2$; if it were
  possible to find large primes with similar properties, the gain
  would be spectacular.}, %
its efficiency is bound to receive only minor improvements in the
coming years. %
In particular, this poses a problem for IoT and other embedded
devices, where SIDH is still unsuitable owing to its large memory and
CPU requirements. %

On the other hand, CSIDH is still very young, and a lot of
optimization avenues are yet to be explored. %
In particular, CSIDH still lacks a constant-time implementation. %
The abysmal performance of the ordinary curve
Couveignes--Rostovtsev--Stolbunov protocol could also use some
improvements, although I am out of ideas at the moment.

In the CSIDH setting, different contexts call for different parameter
choices. %
Note that, while $p$ must grow like $O(n^2)$ due to Kuperberg's
algorithm, the key space is only forced to grow at a much slower rate
of $O(n)$, the best available attacks being the same claw finding
algorithms used against SIDH. %
While the authors of~\cite{10.1007/978-3-030-03332-3_15} have the key-space
grow at the same rate as the prime $p$, it is more convenient for
signatures to have a smaller key space~\cite{cryptoeprint:2018:824}. %
This of course leads to a probability distribution on $\Ell_q(\O)$
very far from uniform, potentially affecting security proofs. %
It is an interesting problem to study the various compromises that can
be made on parameters, and their impact on security.

\paragraph{Security.}
Obviously, confidence in isogeny based cryptography can only be gained
through more research on security. %

This means, of course, working on attacks. %
A fundamental topic, at the moment, is establishing the quantum
security of CSIDH. %
Some preliminary work has been done
in~\cite{cryptoeprint:2018:537,BIJ18,Jao-etal-kuperberg-2018}, but a consensus has yet
to be reached. %

Concerning SIDH, it is interesting that the only recent result on
generic attacks shows that SIDH is potentially \emph{more} secure than
originally thought~\cite{cryptoeprint:2018:313}. %
It is known that an efficient algorithm to compute endomorphism rings
of supersingular curves would also break
SIDH~\cite{galbraithsecurity}, however the currently best algorithms
for this problem~\cite{cervino04,kohel} have much worse
complexity than other attacks on SIDH. %
It would be extremely interesting to look for sub-exponential
algorithms for computing endomorphism rings of supersingular curves,
or alternatively produce convincing arguments for why this is not
possible.

However, none of the known attacks on SIDH exploits the ``auxiliary''
information transmitted by the protocol in the form of torsion
points. %
Some work in this direction has been done by
Petit~\cite{10.1007/978-3-319-70697-9_12}, but no direct impact on
SIDH has been demonstrated. %
In particular, there seems to be absolutely no research on using the
auxiliary information in a quantum algorithm. %

Whether quantum computers, Tate's theorem, Couveignes' algorithm, or a
combination of all can help crack the security of SIDH is certainly
one of the most fascinating topics in isogeny based cryptography.

Besides key recovery, other kinds of attacks are also interesting. %
The most celebrated one is Galbraith, Petit, Shani and Ti's key
learning attack against the static version of
SIDH~\cite{galbraithsecurity}, showing that key validation for SIDH is
indeed hard. %
Other attack models, e.g., side channel attacks, have also been
investigated~\cite{gelin2017loop,ti2017fault}. %
These efforts remain sporadic, and more work is needed in these
directions. %

Finally, more security proofs would help consolidate trust in
isogenies. %
The security assumption of SIDH being so \emph{ad hoc}, more work on
security reductions, such
as~\cite{galbraithsecurity,10.1007/978-3-319-78372-7_11}, could help build
trust by reducing security to more ``natural'' problems. %
CSIDH, on the other hand, benefits from a much nicer hardness
assumption, although key distribution is often an issue for security
proofs: it is not clear how much its security is affected by more
aggressive parameters deviating considerably from the uniform
distribution. %
Given the intended use of these protocols, proofs of quantum security
are another obvious target for research.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\appendix
\def\appendixpagename{Appendix: five peer-reviewed research articles}
\appendixpage*

\makeatletter
\defbibheading{subbib}[References]{\section[#1][#1]{#1 for ``\leftmark''}}
\makeatother
\def\article#1{{
  \input{#1}
  \printbibliography[segment=\therefsegment,heading=subbib]
}}

\article{explicit_isogenies/explicit_isogenies}
\article{ff_compositum/ff_compositum}
\article{ffisom/ffisom}
\article{sidh/sidh}
\article{crs/crs}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\backmatter
\printbibliography

\end{document}

% LocalWords:  isogeny isogenies morphism surjective projective Hasse
% LocalWords:  preimage bijection cryptosystems univariate Decisional
% LocalWords:  isomorphisms isogenous Schoof's decisional bivariate
% LocalWords:  precomputed  abelian Vélu's Elkies Couveignes Lercier
% LocalWords:  Schoof endomorphism Frobenius supersingular Kohel SIDH
% LocalWords:  diagonalizing diagonalizable diagonalization morphisms
% LocalWords:  undirected bathymeter endomorphisms tensored subgraph
% LocalWords:  quotienting eigenspace coprime submodule Atkin Cayley
% LocalWords:  cryptographic codomain invertible diagonalizes CSIDH
% LocalWords:  expander expanders polynomially invariants injective
% LocalWords:  cryptosystem instantiations dihedral cryptology monic
% LocalWords:  cyclotomic embeddings asymptotical incrementality
% LocalWords:  surjection subfields exponentiations Lenstra SageMath
% LocalWords:  Kummer Shoup composita monomial automorphisms
% LocalWords:  Allombert Allombert's reproducibility combinatorial
% LocalWords:  quaternion automorphism monography Rostovtsev
% LocalWords:  Stolbunov computable