poly.tex

\documentclass[10pt]{article}

\usepackage[a4paper]{geometry}
\usepackage[english]{babel}
\usepackage{array}
\usepackage{amsmath,amsthm,amsfonts,amssymb}
\usepackage{unicode}
\usepackage{subcaption}

\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, Elliptic curves, Isogenies},
}

\usepackage[type={CC},modifier={by-nc},imagemodifier={-eu},version={4.0},imagewidth=5em]{doclicense}
\usepackage{fancyhdr}
\usepackage{tabularx}
\usepackage{comment}

\usepackage{algorithmic}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}
\algsetup{linenodelimiter=.}

\usepackage{tikz}
\usetikzlibrary{arrows,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)}}}}

\newcommand{\axes}[4]{
  \clip (#1,#3) rectangle (#2,#4);
  \draw [thin, gray, -latex] (#1,0) -- (#2,0);% Draw x axis
  \draw [thin, gray, -latex] (0,#3) -- (0,#4);% Draw y axis
}

\newcommand{\lattice}[3][2pt]{
  \draw[style=help lines,dashed] (#2-1,#2-1) grid[step=1] (#3+1,#3+1);
  \foreach \x in {#2,...,#3}{
    \foreach \y in {#2,...,#3}{
      \node[draw,circle,inner sep=#1,fill] at (\x,\y) {};
      % Places a dot at those points
    }
  }
}

% theorem environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{problem}{Problem}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{exercise}{Exercise}[part]

\DeclareMathOperator{\Aut}{Aut} % automorphism group
\DeclareMathOperator{\End}{End} % endomorphism ring
\DeclareMathOperator{\Hom}{Hom} % homset
\DeclareMathOperator{\Tr}{Tr} % finite field trace
\DeclareMathOperator{\Gal}{Gal} % Galois group
\DeclareMathOperator{\ord}{ord} % order of an element
\DeclareMathOperator{\lcm}{lcm} % least common multiple
\DeclareMathOperator{\norm}{N} % norm
\DeclareMathOperator{\nrd}{nrd} % reduced norm
\DeclareMathOperator{\discrd}{discrd} % reduced discriminant
\DeclareMathOperator{\loglog}{loglog}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\polylog}{polylog}
\DeclareMathOperator{\im}{Im} % imaginary part
\DeclareMathOperator{\re}{Re} % real part
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\PGL}{PGL}
\DeclareMathOperator{\SL}{SL}
\DeclareMathOperator{\Cl}{Cl}
\DeclareMathOperator{\Ell}{Ell}
\DeclareMathOperator{\rk}{rk} % rank
\DeclareMathOperator{\Pic}{Pic} %Picard group

\def\A{\ensuremath{\mathbb{A}}}
\def\P{\ensuremath{\mathbb{P}}}
\def\F{\ensuremath{\mathbb{F}}}
\def\Q{\ensuremath{\mathbb{Q}}}
\def\Z{\ensuremath{\mathbb{Z}}}
\def\O{\ensuremath{\mathcal{O}}}
\def\tildO{\ensuremath{\tilde{O}}}
\def\euler{\ensuremath{\varphi}}
\def\a{\ensuremath{\mathfrak{a}}}
\def\mat#1{\left(\begin{smallmatrix}#1\end{smallmatrix}\right)}
\newcommand{\leg}[2]{\left(\frac{#1}{#2}\right)}

\newcommand{\IR}[1][]{\ensuremath{{\mathcal{E}\texttt{#1}}}}

\newcommand{\bl}[1]{\textcolor{blue}{#1}}
\newcommand{\rd}[1]{\textcolor{red}{#1}}

\title{Mathematics of Isogeny Based Cryptography}

\usepackage[blocks]{authblk}
\renewcommand\Affilfont{\normalsize}

\author{Luca De Feo}
\affil{
  \textcolor{gray}{Université de Versailles, France}\\
  \textcolor{gray}{Inria Saclay, Palaiseau, France}\\
  IBM Research Europe, Z\"urich, Switzerland\\
  \url{https://defeo.lu/}
}

\author{Marc Houben}
\affil{
  Universiteit Leiden, Netherlands\\
  KU Leuven, Belgium
}

\date{}

\begin{document}

\maketitle

\begin{center}
  \begin{tabular}{r @{~--~} l}
    \color{gray}v1 & \color{gray}May 2017, Thi\`es, Senegal\\
    \color{gray}v2 & \color{gray}August 2019, W\"urzburg, Germany\\
    v3 & September 2024, Popayan, Colombia \& Rabat, Morocco \& Cargèse, France
  \end{tabular}
\end{center}

\thispagestyle{fancy}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0.4pt}
\cfoot{}
\lfoot{Stable version of these notes permanently hosted at
  \url{https://arxiv.org/abs/1711.04062}.  \LaTeX{} source code
  available at \url{https://github.com/defeo/MathematicsOfIBC/}.
  \doclicenseThis}

\section*{Preface}

These lecture notes were first written in 2017 for a summer school on
\emph{Mathematics for post-quantum cryptography} held in Thiès,
Senegal, under the patronage of the \emph{\'Ecoles Math\'ematiques
  Africaines} program and of \href{https://www.cimpa.info/}{CIMPA}.
This version is archived as~\cite{defeo2017isogenybased}.

The second revision~\cite{defeo2017isogenybased} appeared in 2019 at
the summer school
\href{https://ifm.mathematik.uni-wuerzburg.de/summerschool2019/}{\emph{Graph
    Theory Meets Cryptography}} in W\"urzburg, Germany. %
It largely reorganized contents and added material on the newly
discovered CSIDH. %

This third revision was written between 2022 and 2024 for four summer
schools:
\begin{itemize}
\item \href{https://cryptabit.bit.uni-bonn.de/2022}{crypt@b-it} in
  Bonn, Germany;
\item The \href{https://www.cimpa.info/}{CIMPA} research school on
  \href{http://www.rnta.eu/Popayan2023/}{``Isogenies of elliptic
    curves and their applications to cryptography''} in Popayan,
  Colombia;
\item The \href{https://www.cimpa.info/}{CIMPA} research school on
  \href{http://cimpa.c2si-conference.org/}{``Mathematical aspects of
    post-quantum cryptography''} in Rabat, Morocco; and
\item The introductory summer school to the
  \href{https://www.ihp.fr/}{IHP} thematic trimester on
  \href{https://sites.google.com/york.ac.uk/ihp-pqc-trimester-24/}{Post-Quantum
    Algebraic Cryptography}.
\end{itemize}
Coming after the discovery of polynomial-time attacks on SIDH and a
major reshaping of the entire field, it features several important
changes and the addition of Part~\ref{part:ssingular}. %
It also welcomes a new co-author in Marc Houben, who was first a
student in Bonn and then a lecturer in Popayan.

Over the course of these 7 years, isogeny based cryptography has
evolved from a niche topic into a respectable subfield of public-key
cryptography, going through phases of excitement and of existential
doubt. %
Today isogeny based cryptography is too vast to be taught in a single
week of lectures, hence these notes do not attempt at covering the
entirety of known protocols and attacks. %
Instead, they are meant to give the bases to enter the field and,
hopefully, start doing exciting research.

\paragraph{Acknowledgments.}
These notes wouldn't have existed if not for the summer schools
mentioned above. %
For having organized such wonderful events and supported our lectures,
we would like to thank CIMPA, the Écoles Mathématiques Africaines, the
École Polytechnique de Thiès, and their personnel. %
Jörn Steuding, Katja Mönius, Pascal Stumpf, Steffen Reith, Michael
Meyer, the RheinMain University of Applied Sciences and the University
of Würzburg. %
Michael Nüsken, Sophia Grundner-Culemann, Marcel Tiepelt, Daniel
Loebenberger, Jonathan Lennartz, the b-it (Bonn-Aachen International
Center for Information Technology), CASA (Cyber Security in the Age of
Large-Scale Adversaries), the Fachgruppe KRYPTO and the smashHit
project. %
Marusia Rebolledo, Valerio Talamanca, Carlos Trujillo Solarte, Jhon
Jairo Bravo Grijalba, Cristian Angulo and the Universidad del Cauca. %
Souidi El Mamoun, Damien Stehlé and the University Mohammed V of
Rabbat. Delaram Kahrobaei, Ludovic Perret and the Institut Henri
Poincaré.

Many students have contributed by pointing out mistakes and helping
fixing them. %
We would like to thank, in particular, Simon Masson, Marcel Müller,
Martin Strand, Vadym Fedyukovych, Tomáš Novotny, Sina Schaeffler,
Val\'erien Hatey, Mehdi Kermaoui, Ryan Rueger, and apologize to all
those students whose name we've forgot.

\clearpage
{
  \hypersetup{linkcolor=black}
  \setcounter{tocdepth}{1}
  \tableofcontents
}

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

\clearpage
\part{Elliptic curves and isogenies}

In this part, we review the basic and not-so-basic theory of elliptic
curves. %
Our goal is to summarize the fundamental theorems necessary to
understanding the foundations of isogeny based cryptography. %
A proper treatment of the material covered here would require more
than one book, we thus skip proofs and lots of details to go straight
to the useful theorems. %
The reader in search of a more comprehensive treatment will find more
details~\cite{silverman:elliptic,silverman:advanced,lang1987elliptic,neukirch2013algebraic}. %

Throughout this part we let $k$ be a field, and we denote by $\bar{k}$
its algebraic closure. %

\section{Elliptic curves}
\label{sec:elliptic-curves}

Elliptic curves are smooth projective curves of genus 1 with a
distinguished point. %
Projective space initially appeared through the process of adding
\emph{points at infinity}, as a method to understand the geometry of
projections (also known as \emph{perspective} in classical
painting). %
In modern terms, we define projective space as the collection of all
lines in affine space passing through the origin.

\begin{definition}[Projective space]
  The \emph{projective space of dimension $n$}, denoted by $\P^n$ or
  $\P^n(\bar{k})$, is the set of all $(n+1)$-tuples
  \[(x_0,\dots,x_n) ∈ \bar{k}^{n+1}\] %
  such that $(x_0,\dots,x_n) ≠ (0,\dots,0)$, taken modulo the
  equivalence relation
  \[(x_0,\dots,x_n) \sim (y_0,\dots,y_n)\] %
  if and only if there exists $λ\in\bar{k}$ such that
  $x_i=λy_i$ for all $i$.
\end{definition}

The equivalence class of $(x_0,\dots,x_n)$ is customarily denoted by
$(x_0:\cdots:x_n)$ and called a \emph{projective point}. %
The set of the \emph{$k$-rational points}, denoted by $\P^n(k)$, is
defined as
\[\P^n(k) = \left\{(x_0:\cdots:x_n)∈\P^n\;\middle|\; x_i ∈ k \text{ for all $i$}\right\}.\] %
By fixing arbitrarily the coordinate $x_n=0$, we define a projective
space of dimension $n-1$, which we call the \emph{hyperplane at
  infinity}; its points are called \emph{points at infinity}.

From now on we suppose that the field $k$ has characteristic different
from $2$ and $3$. %
This has the merit of greatly simplifying the representation of an
elliptic curve. %
For a general definition, see~\cite[Chap.~III]{silverman:elliptic}.

\begin{definition}[Weierstrass equation]
  An \emph{elliptic curve} defined over $k$ is the locus in
  $\P^2(\bar{k})$ of an equation
  \begin{equation}
    \label{eq:weierstrass}
    Y^2Z = X^3 + aXZ^2 + bZ^3,    
  \end{equation}
  with $a,b∈k$ and $4a^3+27b^2\ne0$.

  The point $(0:1:0)$ is the only point on the line $Z=0$; it is
  called the \emph{point at infinity} of the curve.
\end{definition}

It is customary to write Eq.~\eqref{eq:weierstrass} in \emph{affine
  form}. %
By defining the coordinate functions $x=X/Z$ and $y=Y/Z$, we
equivalently define the elliptic curve as the locus of the equation
\[y^2 = x^3 + ax +b,\]
plus the point at infinity $\O=(0:1:0)$.

In characteristic different from $2$ and $3$, we can show that any
smooth projective curve of genus $1$ with a distinguished point $\O$
is isomorphic to a Weierstrass equation by sending $\O$ onto the point
at infinity $(0:1:0)$.

\begin{figure}
  \centering
  \hfill
  %% 
  \begin{tikzpicture}[domain=-2.4566:4,samples=100,yscale=3/8,xscale=3/4]
    \draw plot (\x,{sqrt(\x*\x*\x-4*\x+5)});
    \draw plot (\x,{-sqrt(\x*\x*\x-4*\x+5)});

    \draw[thin,gray,-latex] (0,-7) -- (0,7);
    \draw[thin,gray,-latex] (-3,0) -- (4,0);

    \draw (-3,1) -- (4,8/3+3);
    \begin{scope}[every node/.style={draw,circle,inner sep=1pt,fill},cm={1,2/3,0,0,(0,3)}]
      \node at (-2.287980,0) {};
      \node at (-0.535051,0) {};
      \node at (3.267475,0) {};
    \end{scope}
    \begin{scope}[every node/.style={yshift=0.3cm},cm={1,2/3,0,0,(0,3)}]
      \node at (-2.287980,0) {$P$};
      \node at (-0.535051,0) {$Q$};
      \node at (3.267475,0) {$R$};
    \end{scope}

    \draw[dashed] (3.267475,3.267475*2/3+3) -- (3.267475,-3.267475*2/3-3) 
    node[draw,circle,inner sep=1pt,fill] {}
    node[xshift=-0.1cm,anchor=east] {$P+Q$};
  \end{tikzpicture}
  %% 
  \hfill
  %% 
  \begin{tikzpicture}[domain=-2.4566:4,samples=100,yscale=3/8,xscale=3/4]
    \draw plot (\x,{sqrt(\x*\x*\x-4*\x+5)});
    \draw plot (\x,{-sqrt(\x*\x*\x-4*\x+5)});

    \draw[thin,gray,-latex] (0,-7) -- (0,7);
    \draw[thin,gray,-latex] (-3,0) -- (4,0);
    
    \def\c{3.269524}
    \def\P{-1.398674}
    \def\R{2.908459}
    \draw (-3,-1+\c) -- (4,4/3+\c);
    \begin{scope}[every node/.style={draw,circle,inner sep=1pt,fill},cm={1,1/3,0,0,(0,3.269524)}]
      \node at (\P,0) {};
      \node at (\R,0) {};
    \end{scope}
    \begin{scope}[every node/.style={yshift=0.3cm},cm={1,1/3,0,0,(0,3.269524)}]
      \node at (\P,0) {$P$};
      \node at (\R,0) {$R$};
    \end{scope}

    \draw[dashed] (\R,\R/3+\c) -- (\R,-\R/3-\c) 
    node[draw,circle,inner sep=1pt,fill] {}
    node[xshift=-0.1cm,anchor=east] {$[2]P$};
  \end{tikzpicture}
  %%
  \hfill
  \strut
  
  \caption{An elliptic curve defined over $ℝ$, and the geometric
    representation of its group law.}
  \label{fig:weierstrass}
\end{figure}

Now, since any elliptic curve is defined by a cubic equation, Bézout's
theorem tells us that any line in $\P^2$ intersects the curve in
exactly three points, taken with multiplicity. %
We define a group law by requiring that three co-linear points sum to
zero. %

\begin{definition}
  Let $E\;:\;y^2=x^3+ax+b$ be an elliptic curve. Let $P_1=(x_1,y_1)$
  and $P_2=(x_2,y_2)$ be two points on $E$ different from the point at
  infinity, then we define a composition law $⊕$ on $E$ as
  follows:
  \begin{itemize}
  \item $P ⊕ \O = \O ⊕ P = P$ for any point $P∈E$;
  \item If $x_1=x_2$ and $y_1=-y_2$, then $P_1⊕P_2 = \O$;
  \item Otherwise set
    \[λ =
      \begin{cases}
        \frac{y_2-y_1}{x_2-x_1} &\text{if $P≠Q$,}\\
        \frac{3x_1^2+a}{2y_1} &\text{if $P=Q$,}
      \end{cases}
    \]
    then the point $(P_1⊕P_2)=(x_3,y_3)$ is defined by
    \begin{align*}
      x_3 &= λ^2 - x_1 - x_2,\\
      y_3 &= -λx_3 - y_1 + λx_1.
    \end{align*}
  \end{itemize}
\end{definition}

It can be shown that the above law defines an Abelian group, thus we
will simply write $+$ for $⊕$. %
The $n$-th scalar multiple of a point $P$ will be denoted by $[n]P$. %
When $E$ is defined over $k$, the subgroup of its \emph{rational
  points over $k$} is customarily denoted $E(k)$. %
Figure~\ref{fig:weierstrass} shows a graphical depiction of the group
law on an elliptic curve defined over $ℝ$.

We now turn to the group structure of elliptic curves. %
The torsion part is easily characterized.

\begin{proposition}
  Let $E$ be an elliptic curve defined over an algebraically closed
  field $k$, and let $m≠0$ be an integer. %
  The $m$-torsion group of $E$, denoted by $E[m]$, has the following
  structure:
  \begin{itemize}
  \item $E[m] ≃ (ℤ/mℤ)^2$ if the characteristic of $k$ does not divide
    $m$;
  \item If $p>0$ is the characteristic of $k$, then 
    \[E[p^i] ≃
      \begin{cases}
        ℤ/p^iℤ & \text{for any $i≥0$, or}\\
        \{\O\} & \text{for any $i≥0$.}
      \end{cases}
    \]
  \end{itemize}
\end{proposition}
\begin{proof}
  See~\cite[Coro.~6.4]{silverman:elliptic}. For the characteristic $0$
  case see also Section~\ref{sec:elliptic-curves-over}.
\end{proof}

When $k$ is not algebraically closed, we write $E[m]$ for the
$m$-torsion subgroup of $E(\bar{k})$, i.e.\ the torsion points in the
algebraic closure. %
$E[m]$ may or may not be fully contained in $E(k)$, it is easy to see,
however, that it will always be contained in a finite extension of
$k$ of degree less than $m^2$.

For curves defined over a field of positive characteristic $p$, the
case $E[p]≃ℤ/pℤ$ is called \emph{ordinary}, while the case
$E[p]≃\{\O\}$ is called \emph{supersingular}. %
We shall see alternative characterizations of supersingularity in
Sections~\ref{sec:ec-over-ff} and~\ref{sec:end(E)}.

The free part of the group is much harder to characterize. %
We have some partial results for elliptic curves over number fields.

\begin{theorem}[Mordell-Weil]
  Let $k$ be a number field, the group $E(k)$ is finitely generated.
\end{theorem}

However the exact determination of the rank of $E(k)$ is somewhat
elusive: we have algorithms to compute the rank of most elliptic
curves over number fields; however, an exact formula for such rank is
the object of the
\href{https://en.wikipedia.org/wiki/Birch_and_Swinnerton-Dyer_conjecture}{\it
  Birch and Swinnerton-Dyer conjecture}, one of the
\href{https://en.wikipedia.org/wiki/Millennium_Prize_Problems}{\it
  Clay Millenium Prize Problems}.

\section{Maps between elliptic curves}

We now focus on maps between elliptic curves. %
We are mostly interested in maps that preserve both facets of elliptic
curves: as projective varieties, and as groups. %

We first look into invertible algebraic maps, that is linear changes
of coordinates that preserve the Weierstrass form of the equation. %
Because linear maps preserve lines, it is immediate that they also
preserve the group law. %
It is easily verified that the only such maps take the form
\[(x,y) \mapsto (u^2x', u^3y')\] %
for some $u∈\bar{k}$, thus defining an \emph{isomorphism} between the
curve $y^2=x^3+au^4x+bu^6$ and the curve $(y')^2 = (x')^3 + ax' +
b$. %
Isomorphism classes are traditionally encoded by an invariant, whose
origins can be traced back to complex analysis.

\begin{proposition}[$j$-invariant]
  \label{th:j}
  Let $E:y^2=x^3+ax+b$ be an elliptic curve, and define the
  \emph{$j$-invariant} of $E$ as
  \[j(E) = 1728\frac{4a^3}{4a^3+27b^2}.\] %
  Two curves are isomorphic over the algebraic closure $\bar{k}$ if
  and only if they have the same $j$-invariant.
\end{proposition}

Note that if two curves defined over $k$ are isomorphic over
$\bar{k}$, they are so over an extension of $k$ of degree at most
$6$. %
An isomorphism between two elliptic curves defined over $k$, that is
itself not defined over $k$ is called a \emph{twist}. %
Any curve defined over a non-quadratically-closed field\footnote{A
  field is quadratically closed if every element has square root.} has
\emph{quadratic twists} obtained by taking $u∉k$ such that $u^2∈k$. %
The two curves of $j$-invariant $0$ and $1728$ also have \emph{cubic},
\emph{sextic} and \emph{quartic twists}.

More general algebraic maps, i.e.\ non-linear (and thus not
necessarily invertible) changes of coordinates, between elliptic
curves are called \emph{isogenies}.

\begin{definition}
  Let $E,E'$ be two elliptic curves. %
  An isogeny $\phi:E→E'$ is a non-constant algebraic map of projective
  varieties sending the point at infinity of $E$ onto the point at
  infinity of $E'$.
\end{definition}

Somewhat surprisingly, being algebraic and preserving the point at
infinity is sufficient to make them group morphisms.

\begin{theorem}
  Let $E,E'$ be elliptic curves defined over a field $k$ and let
  $\phi:E→E'$ be an isogeny between them. %
  Then:
  \begin{itemize}
  \item $\phi$ is a group morphism;
  \item $\phi$ has finite kernel;
  \item If $k$ is algebraically closed, $\phi$ is surjective.
  \end{itemize}
\end{theorem}
\begin{proof}
  See~\cite[III, Th.~4.8]{silverman:elliptic}.
\end{proof}

Two curves are called \emph{isogenous} if there exists an isogeny
between them. %
We shall see later that this is an equivalence relation.

Isogenies from a curve to itself are called \emph{endomorphisms}. %
The prototypical endomorphism is the multiplication-by-$m$
endomorphism defined by
\[[m]\;:\; P \mapsto [m]P.\] %
Its kernel is, by definition, the $m$-th torsion subgroup $E[m]$. %

Since they are algebraic group morphisms, we can define addition of
isogenies by $(ϕ+ψ)(P) = ϕ(P)+ψ(P)$, and the resulting map is still an
isogeny. %
Adding to the set of isogenies $E\to E'$ the constant map that sends
every point of $E$ to the point at infinity of $E'$, we thus obtain a
group, denoted by $\Hom(E,E')$. %
Additionally, endomorphisms $E\to E$ support composition, distributing
over addition, hence the set of all endomorphisms forms a ring,
denoted by $\End(E)$.%
\footnote{In short, isogenies are the morphisms in the Abelian
  category of elliptic curves.}

Since each $m∈ℤ$ defines a different multiplication-by-$m$
endomorphism, clearly $ℤ \hookrightarrow \End(E)$. %
But can $\End(E)$ be larger than $ℤ$? %
The reader will have to wait until Section~\ref{sec:end(E)} to know
the answer to this riddle.



\section{Elliptic curves over $ℂ$}
\label{sec:elliptic-curves-over}

To better understand elliptic curves and their morphisms, we take a
moment now to specialize them to the complex numbers.

\begin{definition}[Complex lattice]
  A \emph{complex lattice} $Λ$ is a discrete subgroup of $ℂ$ that
  contains an $ℝ$-basis of $ℂ$.
\end{definition}

Explicitly, a complex lattice is generated by a \emph{basis}
$(ω_1,ω_2)$, such that $ω_1≠λω_2$ for all $λ∈ℝ$, as
\[Λ = ω_1ℤ + ω_2ℤ.\] %
Up to exchanging $ω_1$ and $ω_2$, we can assume that $\im(ω_1/ω_2)>0$;
we then say that the basis has \emph{positive orientation}. %
A positively oriented basis is obviously not unique, though.

\begin{proposition}
  \label{th:basis-change}
  Let $Λ$ be a complex lattice, and let $(ω_1,ω_2)$ be a positively
  oriented basis, then any other positively oriented basis
  $(ω_1',ω_2')$ is of the form
  \begin{align*}
    ω_1' &= aω_1 + bω_2,\\
    ω_2' &= cω_1 + dω_2,
  \end{align*}
  for some matrix
  $\left(\begin{smallmatrix}a&b\\c&d\end{smallmatrix}\right)∈\SL_2(ℤ)$.
\end{proposition}
\begin{proof}
  See~\cite[I, Lem.~2.4]{silverman:advanced}.
\end{proof}

\begin{definition}[Complex torus]
  Let $Λ$ be a complex lattice, the quotient $ℂ/Λ$ is called a
  \emph{complex torus}.
\end{definition}

\begin{figure}
  \centering
  \begin{tikzpicture}[scale=2]
    \axes{-1}{3.5}{-0.5}{3}

    \begin{scope}[/lattice={1}{0.2}{0.4}{0.7}]
      \draw[fill,black!10] (0,0) -- (1,0) -- (1,1) -- (0,1) -- (0,0);
      \node at (0.5,0.5) {$ℂ/Λ$};
      \node at (0.9,-0.1) {$ω_2$};
      \node at (-0.1,0.9) {$ω_1$};

      \lattice{-3}{4}
    \end{scope}  
  \end{tikzpicture}

  \caption{A complex lattice (black dots) and its associated complex
    torus (grayed \emph{fundamental domain}).}
  \label{fig:lattice}
\end{figure}

A convex set of class representatives of $ℂ/Λ$ is called a
\emph{fundamental parallelogram}. %
Figure~\ref{fig:lattice} shows a complex lattice generated by a
(positively oriented) basis $(ω_1,ω_2)$, together with a fundamental
parallelogram for $ℂ/(ω_1,ω_2)$. %
The additive group structure of $ℂ$ carries over to $ℂ/Λ$, and can be
graphically represented as operations on points inside a fundamental
parallelogram. %
This is illustrated in Figure~\ref{fig:lattice-arith}.

\begin{figure}
  \centering
  \begin{tikzpicture}[scale=1.8]
    \axes{-0.5}{3.5}{-0.5}{3}

    \begin{scope}[/lattice={1}{0.2}{0.4}{0.7}]
      \lattice{-3}{4}

      \node[red] at (0.7,0.65) {$a$}; 
      \node[draw,circle,inner sep=1pt,fill,red] at (0.8,0.5) {};
      \node[red] at (0.2,0.9) {$b$}; 
      \node[draw,circle,inner sep=1pt,fill,red] at (0.3,0.7) {};
      
      \node[draw,circle,inner sep=1pt,fill,red] at (1.1,1.2) {};

      \draw[red,thin,dotted] (0,0) -- (0.8,0.5) -- (1.1,1.2)
      (0,0) -- (0.3,0.7) -- (1.1,1.2);          

      \node[red] at (0.2,0.3) {$a+b$}; 
      \node[draw,circle,inner sep=1pt,fill,red] at (0.1,0.2) {};
    \end{scope}  
  \end{tikzpicture}
  %%
  \hfill
  %%
  \begin{tikzpicture}[scale=1.8]
    \axes{-0.5}{3.5}{-0.5}{3}

    \begin{scope}[/lattice={1}{0.2}{0.4}{0.7}]
      \lattice{-3}{4}
      
      \node[red,yshift=0.2cm] at (0.8,0.6) {$a$}; 
      \draw[red] (0.8,0.6) node[fill,circle,inner sep=1pt] {};

      \draw[red,dotted] (0,0) -- (1.6,1.2) node[fill,circle,inner sep=1pt] {} 
      -- (2.4,1.8) node[fill,circle,inner sep=1pt] {};

      \node[red,yshift=0.3cm] at (0.4,0.8) {$[3]a$}; 
      \draw[red] (0.4,0.8) node[fill,circle,inner sep=1pt] {};
    \end{scope}
  \end{tikzpicture}
  \caption{Addition (left) and scalar multiplication (right) of points
    in a complex torus $ℂ/Λ$.}
  \label{fig:lattice-arith}
\end{figure}

\begin{definition}[Homothetic lattices]
  Two complex lattices $Λ$ and $Λ'$ are said to be \emph{homothetic}
  if there is a complex number $α∈ℂ^{×}$ such that $Λ=αΛ'$.
\end{definition}

Geometrically, applying a homothety to a lattice corresponds to zooms
and rotations around the origin. %
We are only interested in complex tori up to homothety; to classify
them, we introduce the \emph{Eisenstein series of weight $2k$},
defined as
\[G_{2k}(Λ) = \sum_{ω∈Λ\setminus\{0\}}ω^{-2k}.\]
It is customary to set
\[g_2(Λ) = 60G_4(Λ), \quad g_3(Λ) = 140G_6(Λ);\] %
when $Λ$ is clear from the context, we simply write $g_2$ and $g_3$.

\begin{theorem}[Modular $j$-invariant]
  \label{th:modular-j}
  The \emph{modular $j$-invariant} is the function on complex lattices
  defined by
  \[j(Λ) = 1728 \frac{g_2(Λ)^3}{g_2(Λ)^3 - 27g_3(Λ)^2}.\] %
  Two lattices are homothetic if and only if they have the same
  modular $j$-invariant.
\end{theorem}
\begin{proof}
  See~\cite[I, Th.~4.1]{silverman:advanced}.
\end{proof}

It is no chance that the invariants classifying elliptic curves and
complex tori look very similar. %
Indeed, we can prove that the two are in one-to-one correspondence.

\begin{definition}[Weierstrass $℘$ function]
  Let $Λ$ be a complex lattice, the \emph{Weierstrass $℘$ function}
  associated to $Λ$ is the series
  \[℘(z;Λ) = \frac{1}{z^2} + \sum_{ω∈Λ\setminus\{0\}} \left(\frac{1}{(z-ω)^2} - \frac{1}{ω^2}\right).\]
\end{definition}

\begin{theorem}
  \label{th:weierstrass-p}
  The Weierstrass function $℘(z;Λ)$ has the following properties:
  \begin{enumerate}
  \item It is an \emph{elliptic function} for $Λ$, i.e.
    $℘(z) = ℘(z+ω)$ for all $z∈ℂ$ and $ω∈Λ$.
  \item Its Laurent series around $z=0$ is
    \[℘(z) = \frac{1}{z^2} + \sum_{k=1}^∞(2k+1)G_{2k+2}z^{2k}.\]
  \item It satisfies the differential equation
    \[℘'(z)^2 = 4℘(z)^3 - g_2℘(z) - g_3\]
    for all $z∉Λ$.
  \item The curve
    \[E\;:\;y^2=4x^3 - g_2x - g_3\]
    is an elliptic curve over $ℂ$. The map
    \begin{align*}
      ℂ/Λ &\to E(ℂ),\\
      0 &\mapsto (0:1:0),\\
      z &\mapsto (℘(z):℘'(z):1)
    \end{align*}
    is an isomorphism of Riemann surfaces and a group morphism.
  \end{enumerate}
\end{theorem}
\begin{proof}
  See~\cite[VI, Th.~3.1, Th.~3.5, Prop.~3.6]{silverman:elliptic}.
\end{proof}

By comparing the two definitions for the $j$-invariants, we see that
$j(Λ)=j(E)$. %
So, for any homothety class of complex tori, we have a corresponding
isomorphism class of elliptic curves. %
The converse is also true.

\begin{theorem}[Uniformization theorem]
  Let $a,b∈ℂ$ be such that $4a^3+27b^2≠0$, then there is a unique
  complex lattice $Λ$ such that $g_2(Λ) = -4a$ and $g_3(Λ) = -4b$.
\end{theorem}
\begin{proof}
  See~\cite[I, Coro.~4.3]{silverman:advanced}.
\end{proof}

Using the correspondence between elliptic curves and complex tori, we
now have a new perspective on their group structure. %
Looking at complex tori, it becomes immediately evident why the
torsion part has rank $2$, i.e.\ why $E[m]≃(ℤ/mℤ)^2$. %
This is illustrated in Figure~\ref{fig:torsion}; in the picture we see
two lattices $Λ$ and $Λ'$, generated respectively by the black and the
red dots. %
We already defined the multiplication-by-$m$ map of $Λ$ as
$[m]:z \mapsto mz \bmod Λ$. %
This map is the same as reducing
\begin{align*}
  ℂ/Λ &\to ℂ/Λ',\\
  z &\mapsto z \bmod Λ'
\end{align*}
first, and then composing with the homothety $Λ = mΛ'$.

\begin{figure}

  \begin{subfigure}{.45\textwidth}
    \centering
    
    \begin{tikzpicture}[scale=1.2]
      \axes{-0.3}{4.5}{-0.5}{4};

      \begin{scope}[/lattice={3}{0.6}{1.2}{2.1}]
        \lattice{-1}{2}

        \foreach \i in {0,...,2} {
          \foreach \j in {0,...,2} {
            \draw[red] (\i/3,\j/3) node[fill,circle,inner sep=1pt] {};
          }
        }
        \draw[red] (0,0) -- (1/3,0) node[yshift=0.2cm] {$a$};
        \draw[red] (0,0) -- (0,1/3) node[yshift=0.2cm] {$b$};

        \draw[blue] (0.8,0.5) node[fill,circle,inner sep=1pt] {}
        node[yshift=0.2cm] {\scriptsize $z$}
        (2/15,1/6) node[fill,circle,inner sep=1pt] {}
        node[anchor=west,xshift=-0.2cm,yshift=0.2cm] {\scriptsize $z \bmod aℤ+bℤ$}
        (0.4,0.5) node[fill,circle,inner sep=1pt] {}
        node[yshift=0.2cm] {\scriptsize $3z$};
      \end{scope}
    \end{tikzpicture}  
    \caption{$3$-torsion group on a complex torus (red
      points), with two generators $a$ and $b$, and action of the
      multiplication-by-$3$ map (blue dots).}
    \label{fig:torsion}
  \end{subfigure}
  %%
  \hfill
  %%
  \begin{subfigure}{.45\textwidth}
    \centering
    \begin{tikzpicture}[scale=1.2]
      \axes{-0.3}{4.5}{-0.5}{4};
      
      \begin{scope}[/lattice={3}{0.6}{1.2}{2.1}]
        \lattice{-1}{2}

        \draw[red] (0,0) -- (1/3,0) node[yshift=0.3cm] {$a$};
        \draw[green] (0,0) -- (0,1/3) node[fill,circle,inner sep=1pt] {}
        node[yshift=0.3cm] {$b$};

        \draw[blue] (0.8,0.5) node[fill,circle,inner sep=1pt] {}
        node[yshift=0.3cm] {$z$};
      \end{scope}
      
      \begin{scope}[/lattice={1}{0.2}{1.2}{2.1}]
        \begin{scope}[opacity=0.5,red]
          \lattice[1pt]{-3}{5}
        \end{scope}

        \draw[blue] (0.4,0.5) node[fill,circle,inner sep=1pt] {}
        node[yshift=0.3cm] {$ϕ(z)$};
      \end{scope}
    \end{tikzpicture}
    
    \caption{Isogeny from $ℂ/Λ$ (black dots) to $ℂ/Λ'$ (red dots)
      defined by $ϕ(z)=z \bmod Λ'$. The kernel of $ϕ$ is contained
      in $(ℂ/Λ)[3]$ and is generated by $a$. The kernel of the dual
      isogeny $\hat{ϕ}$ is generated by the vector $b$ in $Λ'$.}
    \label{fig:isogeny}
  \end{subfigure}
  
  \caption{Maps between complex tori.}
\end{figure}

Within this new perspective, isogenies are a mild generalization of
scalar multiplications. %
Whenever two lattices $Λ,Λ'$ verify $αΛ⊂Λ'$, there is a well defined
map
\begin{align*}
   ϕ_α : ℂ/Λ &\to ℂ/Λ',\\
  z &\mapsto αz \bmod Λ'
\end{align*}
that is holomorphic and also a group morphism. %
One example of such maps is given in Figure~\ref{fig:isogeny}: there,
$α=1$ and the red lattice strictly contains the black one; the map is
simply defined as reduction modulo $Λ'$. %
It turns out that these maps are exactly the isogenies of the
corresponding elliptic curves.

\begin{theorem}
  Let $E,E'$ be elliptic curves over $ℂ$, with corresponding lattices
  $Λ,Λ'$. %
  There is a bijection between the set of isogenies from $E$ to $E'$
  and the set of maps $ϕ_α$ for all $α$ such that $αΛ⊂Λ'$.
\end{theorem}
\begin{proof}
  See~\cite[VI, Th.~4.1]{silverman:elliptic}.
\end{proof}

Looking again at Figure~\ref{fig:isogeny}, we see that there is a
second isogeny $\hat{ϕ}$ from $Λ'$ to $Λ/3$, whose kernel is generated
by $b∈Λ'$. %
The composition $\hat{ϕ}∘ϕ$ is an endomorphism of $ℂ/Λ$, up to the
homothety sending $Λ/3$ to $Λ$, and we verify that it corresponds to
the multiplication-by-$3$ map. %
In this example, the kernels of both $ϕ$ and $\hat{ϕ}$ contain $3$
elements, and we say that $ϕ$ and $\hat{ϕ}$ have \emph{degree} $3$. %
Although not immediately evident from the picture, this same
construction can be applied to any isogeny. %
The isogeny $\hat{ϕ}$ is called the \emph{dual} of $ϕ$. %
Dual isogenies exist not only in characteristic $0$, but also for any
base field, as we shall see in Section~\ref{sec:isogenies}.

Under which conditions does an isogeny become an endomorphism? By
virtue of the last theorem, there is a one-to-one correspondence
between the endomorphisms $E\to E$ and the complex numbers $α$ such
that $αΛ⊂Λ$. %
In general, the only possible choices are given by $α$ an integer,
corresponding to scalar multiplications. %
For some lattices, however, something ``special'' happens; we shall
study this case in Sections~\ref{sec:end(E)} and~\ref{sec:compl-mult}.



\section{Elliptic curves over finite fields}
\label{sec:ec-over-ff}

In this section we shift our attention to elliptic curves defined over
a finite field, which are the main objects manipulated in
cryptography. %
From now on we will use $q$ to denote a power of a prime $p$, and
$\F_q$ do denote a finite field with $q$ elements.

Obviously, the group of rational points of a curve defined over a
finite field is finite. %
Because every element of $\bar{\F}_q$ is defined over a finite
extension of $\F_q$, the algebraic group $E(\bar{\F}_q)$ only contains
torsion elements, and we have already characterized precisely the
structure of the torsion part of $E$.

For curves over finite fields, the Frobenius endomorphism plays a very
special role, and governs much of their structure.

\begin{definition}[Frobenius endomorphism]
  Let $E$ be an elliptic curve defined over a field with $q$ elements,
  its \emph{Frobenius endomorphism}, denoted by $π$, is the map that
  sends
  \[(X:Y:Z) \mapsto (X^q:Y^q:Z^q).\]
\end{definition}

\begin{proposition}
  \label{th:frob}
  Let $π$ be the Frobenius endomorphism of $E$. Then:
  \begin{itemize}
  \item $\ker π = \{\O\}$;
  \item $\ker (π-1) = E(k)$.
  \end{itemize}
\end{proposition}

\begin{theorem}[Hasse]
  \label{th:hasse}
  Let $E$ be an elliptic curve defined over a finite field with $q$
  elements. %
  Its Frobenius endomorphism $π$ satisfies a quadratic equation
  \begin{equation}
    \label{eq:frob}
    π^2 - tπ + q = 0,
  \end{equation}
  for some $|t|≤2\sqrt{q}$.
\end{theorem}
\begin{proof}
  See~\cite[V, Th.~2.3.1]{silverman:elliptic}.
\end{proof}

The coefficient $t$ in the equation is called the \emph{trace} of
$π$. %
It gives an alternative characterization of supersingularity.

\begin{proposition}
  An elliptic curve $E$ defined over a finite field of characteristic
  $p$ is supersingular if and only if $p$ divides the trace of its
  Frobenius endomorphism.
\end{proposition}

By replacing $π=1$ in eq.~\eqref{eq:frob}, we immediately obtain the
cardinality of $E$ as $\#E(k) = \#\ker(π-1) = q+1-t$. %

\begin{corollary}
  Let $E$ be an elliptic curve defined over a finite field $k$ with $q$
  elements, then
  \[|\#E(k) - q - 1| ≤ 2\sqrt{q}.\]
\end{corollary}

It turns out that the cardinality of $E$ over its \emph{base field}
$k$ determines its cardinality over any finite extension of it. %
This is a special case of Weil's famous conjectures, proven by Weil
himself in 1949 for Abelian varieties, and more generally by Deligne
in 1973.

\begin{definition}
  Let $V$ be a projective variety defined over a finite field $\F_q$,
  its \emph{zeta function} is the power series
  \[Z(V/\F_q; T) = \exp\left(\sum_{n=1}^∞\#V(\F_{q^n})\frac{T^n}{n}\right).\]
\end{definition}

\begin{theorem}
  \label{th:weil}
  Let $E$ be an elliptic curve defined over a finite field
  $\F_q$, and let $\#E(\F_q)=q+1-a$. Then
  \[Z(E/\F_q;T) = \frac{1-aT+qT^2}{(1-T)(1-qT)}.\]
\end{theorem}
\begin{proof}
  See~\cite[V, Th.~2.4]{silverman:elliptic}.
\end{proof}



\section{Isogenies}
\label{sec:isogenies}

We now look more in detail at isogenies of elliptic curves. %
We start with some basic definitions.

\begin{definition}[Degree, separability]\label{def:degsep}
  Let $ϕ:E\to E'$ be an isogeny defined over a field $k$, and let
  $k(E),k(E')$ be the function fields of $E,E'$. %
  By composing $\phi$ with the functions of $k(E')$, we obtain a
  subfield of $k(E)$ that we denote by $ϕ^\ast(k(E'))$.

  \begin{enumerate}
  \item The \emph{degree} of $ϕ$ is defined as
    $\deg ϕ = [k(E):ϕ^\ast(k(E'))]$; it is always finite.
  \item $ϕ$ is said to be \emph{separable}, \emph{inseparable}, or
    \emph{purely inseparable} if the extension of function fields is.
  \item If $ϕ$ is separable, then $\deg ϕ = \#\ker ϕ$.
  \item If $ϕ$ is purely inseparable, then $\deg ϕ$ is a power of the
    characteristic of $k$.
  \item Any isogeny can be decomposed as a product of a separable and
    a purely inseparable isogeny.
  \end{enumerate}
\end{definition}
\begin{proof}
  See~\cite[II, Th.~2.4]{silverman:elliptic}.
\end{proof}

In practice, most of the time we will be considering separable
isogenies, and we can take $\deg ϕ := \#\ker ϕ$ as the definition of
the degree. %
Notice that in this case $\deg ϕ$ is the size of any fiber of $ϕ$
(over the algebraic closure). %
When the kernel of a separable isogeny is cyclic we call it a
\emph{cyclic} isogeny, and when then kernel is isomorphic to $ℤ/ℓℤ$ we
call it an $\ell$-isogeny.

\begin{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 a separable $2$-isogeny between curves defined over $ℚ$. %
  It has degree $2$, and its kernel is generated by the point
  $(0,0)$. %

  \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}

  Plotting the isogeny~\eqref{eq:isog-example} over $ℝ$ would be
  cumbersome, however, since the curves are defined by integer
  coefficients, we may reduce the equations modulo a prime $p$, then
  the isogeny descends to an isogeny of curves over $\F_p$. %
  Figure~\ref{fig:isog-example} plots the action of the isogeny after
  reduction modulo $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. %

  It is evident that the isogeny is $2$-to-$1$, however, over $\F_p$,
  we are unable to see all fibers, because the isogeny is only
  surjective over 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 $2$-to-$1$ (algebraic) group morphism of
  $\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. %
\end{example}

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

\begin{proposition}
  \label{prop:isoker}
  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}
\begin{proof}
  See~\cite[Prop.~III.4.12]{silverman:elliptic}
\end{proof}

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'$. %
Conversely, since any non-constant morphism of elliptic curves
necessarily has finite kernel, we have a bijection between the finite
subgroups of a curve $E$ and the isogenies with domain $E$ up to
isomorphisms. %
This correspondence is rich in consequences: it is an easy exercise to
prove the following useful facts. %

\begin{corollary}\ 
  \label{coro:isog-basic}
  \begin{enumerate}
  \item Let $H$ and $G$ be finite subgroups $H ⊂ G ⊂ E$, and
    $ϕ: E \to E/G$. %
    Then $ϕ$ factors as $ψ∘χ$, with $χ : E → E/H$ and
    $ψ : E/H → (E/H)/χ(G)$, up to post-composition by an isomorphism.
  \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$ isogenies of degree $ℓ$ having $E$ for domain,
    up to post-composition with an isomorphism.
  \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]{silverman:elliptic} 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}

\paragraph{Representing and computing isogenies.}
The computational counterpart to the kernel-isogeny correspondence is
given by Vélu's 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. %
  A rational expression for the separable isogeny $ϕ:E→ E/G$ of kernel
  $G$ is given by
  \begin{align*}
    ϕ(P) = \left(
      x(P) + \sum_{Q∈G\setminus\{\O\}}x(P+Q)-x(Q),\quad
      y(P) + \sum_{Q∈G\setminus\{\O\}}y(P+Q)-y(Q)
    \right)
  \end{align*} %
  for any point $P ∉ G$, taking the curve of equation $y^2=x^3+a'x+b'$
  with
  \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*}
  as a representative for $E/G$.
\end{proposition}

Using Vélu's formulas, or one of their
variants~\cite{moody2016analogues,AC:CosHis17,PQCRYPTO:Renes18}, we
can represent isogenies and evaluate them at arbitrary points using an
amount of field operations polynomial in their degree. %
In some favorable cases, an isogeny of degree $d$ can even be
represented in constant space and be evaluated at arbitrary points
using only $\sqrt{d}\polylog(d)$
operations~\cite{bernstein2020faster}. %

We extend this representation to chains of isogenies: we represent
each isogeny in the chain by its kernel, and evaluate it using Vélu's
formulas. %
Thanks to Corollary~\ref{coro:isog-basic}, any isogeny of composite
degree $N$ can thus be stored and evaluated in time polynomial in
$\log(N)$ and the largest prime factor of $N$.

We will later discover more efficient ways to store and evaluate
isogenies, which motivates abstracting away the details of how an
isogeny is actually represented into a definition that focuses on what
one can actually do with the representation.

\begin{definition}[Isogeny representation]
  \label{def:isog-repr}
  Let $\F_q$ be a finite field. %
  An \emph{isogeny evaluator} \IR{} is a pair of polynomial-time
  algorithms:
  \begin{itemize}
  \item $\IR[.valid](\phi)$ taking as input a string
    $\phi\in\{0,1\}^*$ and outputting either a symbol $\bot$ or a
    triple $(E, E', d)$; in the latter case, $E$ and $E'$ are elliptic
    curves defined over $\F_q$ and there exists an isogeny
    $\phi_{\IR}: E\to E'$ of degree $d$.
  \item $\IR[.eval](\phi, P)$ taking as input a string
    $\phi\in\{0,1\}^*$ and a point $P\in E(\F_{q^k})$; if
    $\IR[.valid](\phi) = (E, E', d)$ it outputs the image point
    $\phi_{\IR}(P)\in E'(\F_{q^k})$, otherwise the output is
    undefined.
  \end{itemize}

  In the case that \IR[.valid] does not output $\bot$ and that $\phi$
  is of size polynomial in $\log(q)$ and $d$, the string $\phi$ is
  called an \emph{efficient representation} of $\phi_{\IR}$ (for the
  evaluator \IR).  When the evaluator is clear from context, we will
  omit the subscript in $\phi_{\IR}$ and write $\phi$ for both the
  representation and the isogeny it represents.
\end{definition}


\section{The Weil pairing}
\label{sec:weil-pairing}

The definition below is given for free modules over a ring. %
If the reader feels uncomfortable with rings and modules, they may
think of vector spaces over a field instead.

\begin{definition}
  Let $M_1, M_2$ be free modules over a commutative ring $R$. %
  A bilinear form is a mapping $e:M_1\times M_2\to R$ such that:
  \begin{itemize}
  \item $e(aP,Q) = e(P,aQ) = a\cdot e(P,Q)$,
  \item $e(P+P', Q) = e(P,Q) + e(P',Q)$,
  \item $e(P, Q+Q') = e(P,Q) + e(P,Q')$,
  \end{itemize}
  for all $a\in R$, all $P,P'\in M_1$ and all $Q,Q'\in M_2$.

  A bilinear form is said to be \emph{non-degenerate} if:
  \begin{itemize}
  \item $e(P,Q)=0$ for all $P$ implies $Q=0$, and
  \item $e(P,Q)=0$ for all $Q$ implies $P=0$.
  \end{itemize}

  A bilinear form is said to be \emph{alternating} if $M_1=M_2$ and
  $e(P,P)=0$ for all $P$.
\end{definition}

If instead of taking values in $R$, we define a map
$M_1\times M_2\to M_3$, with the same properties as above, but taking
values in an $R$-module $M_3$, we talk of a bilinear map, or
\emph{pairing}. %

\begin{proposition} 
  Let $E/k$ be an elliptic curve defined over a field $k$, and let $m$
  be a positive integer prime to the characteristic of $k$. %
  Write $\mu_m\subset\bar{k}$ for the subgroup of $m$-th roots of
  unity of the algebraic closure of $k$.
  
  There exist a non-degenerate alternating pairing of $ℤ/mℤ$-modules
  \[e_m:E[m]\times E[m]\to \mu_m,\]
  called the \emph{Weil pairing}.
\end{proposition}

The exact definition of the Weil pairing requires more geometric tools
than we are willing to introduce here (see,
e.g.,~\cite{silverman:elliptic,galbraith2012mathematics} for
details). %
For the sake of these notes, it suffices to recall that the torsion
subgroup $E[m]$ is isomorphic to $(ℤ/mℤ)^2$, i.e.\ is a free module of
rank two. %
On the other hand, the image group $\mu_m$ only has rank one, thus the
Weil pairing is just a bilinear form in disguise\dots and not just any
bilinear form! %
Indeed, under the constraint of being non-degenerate and alternating,
the Weil pairing is, essentially, the $2×2$ determinant form, as the
following proposition shows.

\begin{proposition}
  \label{prop:weil-det}
  Let $M$ be a $ℤ/mℤ$ module of rank 2, and let $(P,Q)$ be a pair of
  generators. %
  Let $e$ be an alternating pairing on $M×M$ taking values in a
  multiplicative group $G$ of order $m$, and let $\zeta = e(P,Q)$. %
  Then
  \[e([a]P + [b]Q, [c]P + [d]Q) =
    \zeta^{\det\left(\begin{smallmatrix}a&b\\c&d\end{smallmatrix}\right)}.\]

  In particular $e$ is non-degenerate if and only if $\zeta$ generates $G$.
\end{proposition}

It is remarkable that the Weil pairings of isogenous curves are
``compatible'' in a precise sense. %
Indeed, it turns out that the dual isogeny is the ``transpose'' in the
sense of bilinear forms.

\begin{theorem}
  Let $E,E'$ be elliptic curves, let $\phi:E\to E'$ be an isogeny,
  $\hat\phi:E'\to E$ its dual, let $m$ be a positive integer. %
  For any $P\in E[m]$ and $Q\in E'[m]$
  \begin{equation}
    \label{eq:pairing-isog}
    e_m'\bigl(\phi(P), Q\bigr) = e_m\bigl(P, \hat\phi(Q)\bigr).
  \end{equation}
  where $e_m$ and $e_m'$ denote the Weil pairing of $E$ and $E'$
  respectively.
\end{theorem}
\begin{proof}
  See~\cite[III.8.2]{silverman:elliptic}.
\end{proof}

\begin{corollary}
  \label{coro:iso-pairing}
  Let $\phi:E\to E'$ be an isogeny of degree $d$. For any
  $m,P,Q$
  \[e_m'\bigl(\phi(P),\phi(Q)\bigr) = e_m(P,Q)^d.\]
\end{corollary}

There exist algorithms to compute the Weil pairing taking a number of
operations over the field of definition of $E[m]$ polynomial (and even
quasi-linear) in $\log(m)$. %
There exist other pairings defined for elliptic curves over finite
fields, which are sometimes faster to compute than the Weil pairing. %
However they are all related, and will not make a difference for our
purposes, thus we will ignore them. %
For a review of known elliptic pairings, addressed to non-specialists,
see~\cite{10.1016/j.dam.2007.12.010}.


\section{The endomorphism ring}
\label{sec:end(E)}

We come back to the question of determining the structure of
$\End(E)$. %
To put the right words on it, we need to recall some background from
algebraic number theory; for an in-depth treatment,
see~\cite{langANT,Voight2018}.

\paragraph{A quadratic number field} 
is a quadratic extension $K$ of the rationals; it is called
\emph{real} if there exists an embedding $K⊂ℝ$, \emph{imaginary}
otherwise. %
All such fields can be expressed as $ℚ(\sqrt{d})$ for some integer
$d$, the \emph{Gaussian integers} $ℚ(i)$ being a typical example of an
imaginary one. %

\begin{definition}[Discriminant]
  Let $d$ be a square free integer, the \emph{discriminant} of the
  quadratic number field $ℚ(\sqrt{d})$ is $d$ if $d=1\bmod 4$, and
  $4d$ otherwise.
\end{definition}

An integer $Δ$ that is the discriminant of a quadratic number field is
called a \emph{fundamental discriminant}.

\begin{definition}
  Let $α = a + b\sqrt{d}$ be an element of a quadratic number field. %
  \begin{itemize}
  \item Its \emph{conjugate} is $\bar{α} = a - b\sqrt{d}$;
  \item Its \emph{norm} is $N(α) = α\bar{α} = a^2 - db^2$;
  \item Its \emph{trace} is $\Tr(α) = α + \bar{α} = 2a$.
  \end{itemize}
\end{definition}

\begin{proposition}
  Let $α$ be an element of a quadratic imaginary field, then it is a
  root of the quadratic polynomial with rational coefficients
  \[x^2 - \Tr(α)x + N(α).\]
\end{proposition}

The elements with integer trace and norm can be seen as a
generalization of the ring $ℤ$ of integers inside $ℚ$.

\begin{definition}[Ring of integers]
  Let $K$ be a quadratic number field,
  an \emph{algebraic integer} of $K$ is an
  element $α∈K$ that is a root of an irreducible monic polynomial with
  integer coefficients. %
  The algebraic integers of $K$ form a ring, called the \emph{ring of
    integers} of $K$.
\end{definition}

For example, $ℤ[i]$ is the ring of integers of $ℚ(i)$; more generally,
if $Δ$ is a fundamental discriminant, the ring of integers of
$ℚ(\sqrt{Δ})$ is $ℤ[δ]$, where $δ=(Δ+\sqrt{Δ})/2$. %

\begin{definition}[Fractional ideals, orders]
  Let $K$ be a quadratic number field. %
  A \emph{fractional ideal} $I ⊂ K$ is a $ℤ$-lattice of rank 2. %
  An \emph{order} $\O ⊂ K$ is a fractional ideal that is also a ring.

  Let $I ⊂ K$ be a fractional ideal, its order is the ring
  \[\O_I = \{ α ∈ K \,|\, Iα ⊂ I \}.\]
  When $I ⊂ \O_I$ we say that $I$ is \emph{integral}. %
  when $I = α\O_I$ for some $α∈K$, we say that $I$ is
  \emph{principal}. %
  If there exists another fractional ideal $I^{-1}$ such that
  $II^{-1} = \O_I$ we say that $I$ is \emph{invertible}.
\end{definition}  

It is clear that $I$ is an $\O_I$-module, and when it is integral we
recover the usual definition of an ideal of $\O_I$. %
In this case, we will omit ``fractional'' and simply call $I$ an
\emph{ideal} of $\O_I$. %
Clearly $I$ is also an $\O$-module for any $\O⊂\O_I$, and we thus say
it is a (fractional) $\O$-ideal. %

We now generalize the concept of norm to an ideal. %
We need a technical definition first.

\begin{definition}[$\gcd$ of rational numbers]
  For two rational numbers $a=m/n,b=r/s$, written such that
  $\gcd(m,n)=1=\gcd(r,s)$, we define their greatest common divisor as
  $\gcd(a,b) := \gcd(m,r)/\lcm(n,s)$.  By extension, we can also
  define the $\gcd$ of an arbitrary subset of $\Q$, as long as the
  least common multiple of the denominators of its elements is finite.
\end{definition}

\begin{proposition}[Ideal norm]
  Let $I$ be a fractional ideal. %
  Its \emph{norm} $N(I)$ is the gcd of the norms of its elements. %
  An ideal is integral if and only if its norm is an integer.
\end{proposition}

By these definitions, the ring of integers $\O_K$ is an order of $K$:
indeed it has $(1,δ)$ as a \emph{basis}, i.e., as a set of $ℤ$-module
generators. %
It is, in fact, the \emph{maximal order} of $K$, i.e.\ it contains
any other order of $K$. %
A more precise statement is the following.

\begin{proposition}
  Let $K$ be a quadratic number field, let $\O_K$ be its ring of
  integers, and let $\O ⊂ \O_K$ be an arbitrary order. %
  The index $f=[\O_K:\O]$ as abelian groups is called the
  \emph{conductor of $\O$}. %
  Then, $\O$ can be written as $\O=ℤ+f\O_K$. %
\end{proposition}  

We generalize the notion of discriminant to any order.

\begin{definition}[Discriminant]
  Let $\O$ be an order with basis $(1,δ)$. %
  Its \emph{discriminant} is $(δ-\bar{δ})^2$, where
  $\bar{δ}$ denotes the complex conjugate of $δ$. %
  It is independent of the choice of a basis.
\end{definition}

\begin{proposition}
  Let $\O$ be an order, let $Δ$ be its discriminant and let $f$ be its
  conductor. %
  Let $Δ_K$ the discriminant of the maximal order, then
  $Δ = f^2Δ_K$. %
  If $\O,\O'$ are two orders of discriminants $Δ,Δ'$, then $\O⊂\O'$ if
  and only if $Δ'|Δ$.
\end{proposition}

Because $\O_K$ is the ``most obvious'' order of $K$, (fractional)
$\O_K$-ideals are often simply called (fractional) ideals of $K$. %

\begin{proposition}
  Any fractional $\O_K$-ideal is invertible.
\end{proposition}


\paragraph{Quaternion algebras} %
are a 4-dimensional generalization of quadratic number fields: like in
number fields, any element satisfies a quadratic equation; unlike
them, they are not fields. The theory on quaternion algebras is very rich,
and possesses deep connections with many objects in number theory, such as
quadratic forms, modular forms, and elliptic curves~\cite{Lam,Voight2018}.

\begin{definition}[Quaternion algebra]
  A \emph{quaternion algebra over $\Q$} is an algebra of the form
  \[K = ℚ + iℚ + jℚ + kℚ,\]
  where the generators satisfy the relations
  \[0\neq i^2\in\Q, \quad 0\neq j^2∈ℚ, \quad k=ij=-ji.\]
  If $i^2 = a$ and $j^2 = b$, we denote such an algebra by
  $\left(\frac{a,b}{\Q}\right)$.
\end{definition}

An arbitrary element of a quaternion algebra can be written as
$\alpha = t + xi  + yj + zk$, where $t,x,y,z\in\Q$.
The \emph{real part}  of such an element is $\re(\alpha) = t$,
the \emph{imaginary part} is $\im(\alpha) = xi + yj + zk$.
The \emph{conjugate} $\overline{\alpha}$ is obtained
by flipping the sign of the imaginary part;
$\overline{\alpha} = t - xi - yj - zk$.
The (reduced) \emph{norm} and \emph{trace} are defined as
\begin{equation*}
N(\alpha) := \alpha\overline{\alpha} = t^2 - ax^2 - by^2 +abz^2, \qquad
\Tr(\alpha) := \alpha + \overline{\alpha} = 2t
\end{equation*}
respectively.\footnote{Although the adjective \emph{reduced} is technically
necessary from a purely mathematical point of view, the terms
\emph{reduced norm} and \emph{norm}, and similarly for the trace,
are often used interchangably in the context of quaternions.}
This motivates the following definition.

\begin{definition}
The \emph{norm form} associated to the quaternion algebra $\left(\frac{a,b}{\Q}\right)$ is the polynomial $t^2 - ax^2 - by^2 + abz^2\in\Q[t,x,y,z]$. 
\end{definition}

Let $p$ be a prime number and let $K$ be a quaternion algebra over $\Q$.
We say that $K$ is \emph{split} at $p$ if $K\otimes\Q_p\cong M_2(\Q_p)$.
This is equivalent to the norm form having a non-trivial zero over $\Q_p$.
Otherwise, we say that the quaternion algebra is \emph{ramified} at $p$.

We say $K$ is \emph{ramified at $\infty$}
if the norm form has no non-trivial zero over $\mathbb{R}$.
This is equivalent to $a,b$ being both negative.

The \emph{reduced discriminant} of a quaternion algebra
is the product of the primes at which it ramifies.
For every prime number $p$, there is, up to isomorphism,
a unique quaternion algebra with discriminant $p$, which we denote
$B_{p,\infty}$. It ramifies exactly at $p$ and $\infty$.

\begin{proposition}
  \label{th:quat-presentation}
  Let $p$ be a prime number, then we can choose the following representations
  for the quaternion algebra $B_{p,\infty}$.
  \begin{enumerate}
  \item $B_{p,\infty} \cong \left(\frac{-1,-1}{\Q}\right)$
    if $p=2$;
  \item $B_{p,\infty} \cong \left(\frac{-1,-p}{\Q}\right)$
    if $p\equiv 3\pmod{4}$;
  \item $B_{p,\infty} \cong \left(\frac{-2,-p}{\Q}\right)$
    if $p\equiv 5\pmod{8}$;
  \item $B_{p,\infty} \cong \left(\frac{-r,-p}{\Q}\right)$
    if $p\equiv 1\pmod{8}$, where $r\equiv 3\pmod{4}$ is a prime number
    that is not a square modulo $p$.
  \end{enumerate}
\end{proposition}
\begin{proof}
  See~\cite{pizer1980}.
\end{proof}

From now onward, our main quaternion algebra of concern will be $B_{p,\infty}$;
it turns out to be the most interesting one in the context of elliptic curves,
because it contains all endomorphism rings of supersingular elliptic curves
over fields of characteristic $p$. However, many of the definitions and results
that follow are equally valid for arbitrary quaternion algebras.


\paragraph{Fractional ideals} in $B_{p,\infty}$ are $\Z$-lattices
$I\subset B_{p,\infty}$ of rank $4$.
The (reduced) \emph{norm} of an ideal is defined as the
$\gcd$ of the (reduced) norms of its elements;
$N(I) = \nrd(I) := \gcd\{N(\alpha)\mid\alpha\in I\}$.
%Exercise: show that this is well-defined (i.e. indeed, the lcms
%of the denominators of the norms is bounded.
If $I\subset J$ are two fractional ideals, then the index $[J:I]$ as
an abelian group equals $\left(N(I)/N(J)\right)^2$.
If $\alpha_1,\alpha_2,\alpha_3,\alpha_4$ is a $\Z$-basis for $I$, then
we define the \emph{reduced discriminant} of $I$ as $\discrd(I) :=
|\det(\Tr(\alpha_i\overline{\alpha_j}))_{1\leq i,j\leq 4}|^{1/2}$;
it is independent of the chosen basis.

\paragraph{Orders} in $B_{p,\infty}$ are fractional ideals that are also
subrings. We say an order $\O\subset B_{p,\infty}$ is \emph{maximal} if
it is not strictly contained in any other order. An order is maximal
if and only if its reduced discriminant is $p$.
Given a fractional ideal $I\subset B_{p,\infty}$,
we denote by $\O_L(I):=\{\alpha\in B_{p,\infty}\mid \alpha I\subset I\}$
its \emph{left order},
and by $\O_R(I):=\{\alpha\in B_{p,\infty}\mid I\alpha\subset I\}$
its \emph{right order}.
We say that $I$ is a fractional left (respectively right) $\O$-ideal if
$\O\subset\O_L(I)$ (respectively $\O\subset\O_R(I)$).
A (left or right) $\O$-ideal $I$ is called \emph{integral} if $I\subset\O$.


\begin{proposition}
  \label{th:quat-max-ord}
  Let $B_{p,∞}$ be represented like in
  Proposition~\ref{th:quat-presentation}. %
  Then
  \begin{equation*}
    \O =
    \begin{cases}
      \left〈\frac{1 + i + j + ij}{2}, i, j, ij \right〉 & \text{if $p = 2$},\\
      \left〈1, i, \frac{1+j}{2}, \frac{i+ij}{2} \right〉 & \text{if $p ≡ 3 \pmod 4$,}\\
      \left〈1, i, \frac{-1+i+j}{2}, \frac{2-i+ij}{4} \right〉 & \text{if $p ≡ 5 \pmod 8$,}\\
      \left〈\frac{1+i}{2}, \frac{j+ij}{2}, \frac{i+cij}{r}, ij\right〉 & \text{if $p ≡ 1 \pmod 8$, where $c^2p = -1 \pmod r$,}
    \end{cases}
  \end{equation*}
  is a maximal order of $B_{p,∞}$.
\end{proposition}
\begin{proof}
  See~\cite[Lemmas~2--4]{kohel2014quaternion}
  or~\cite[Lemmas~2.2--3]{FOCS:Wesolowski21}.
\end{proof}


\paragraph{The endomorphism ring.}
We finally have all the necessary language to classify endomorphism
rings of elliptic curves: they all turn out to be lattices of
rank $1$, $2$ or $4$. A more precise statement is the following.

\begin{theorem}[Deuring]
  \label{th:endring}
  Let $E$ be an elliptic curve defined over a field $k$ of
  characteristic $p$. %
  The ring $\End(E)$ is isomorphic to one of the following:
  \begin{itemize}
  \item $ℤ$;
  \item An order $\O$ in a quadratic imaginary field; in this case we
    say that $E$ has \emph{complex multiplication} by $\O$;
  \item Only if $p>0$, a maximal order $\O$ in $B_{p,\infty}$; in this
    case we say that $E$ has \emph{quaternionic multiplication} by
    $\O$. %
    This happens if and only if $E$ is supersingular.
  \end{itemize}
\end{theorem}
\begin{proof}
  See~\cite[III, Coro.~9.4]{silverman:elliptic}
  and~\cite{kohel}.
\end{proof}

The smallest $ℚ$-algebra containing $\End(E)$, i.e.\ $\End(E)⊗ℚ$, is
called the \emph{endomorphism algebra} of $E$. %
For curves over finite fields, this is entirely determined by the
Frobenius endomorphism, which we recall satisfies a quadratic equation
$π^2 - tπ + q = 0$. %
Indeed we already saw that a curve is supersingular if and only if the
characteristic divides the trace $t$. %
Otherwise the curve is ordinary and $\End(E)$ must contain an
algebraic integer with the same minimal equation, which has
discriminant $Δ_π=t^2-4q<0$, and thus $\End(E)⊂ℚ(\sqrt{Δ_π})$.

The minimal polynomial of Frobenius can be computed in polynomial time
using Schoof's algorithm~\cite{schoof85} (see
Appendix~\ref{sec:appl-point-count}), and thus the endomorphism
algebra can be determined with the same complexity.
Determining the exact order isomorphic to $\End(E)$ is (in general)
much more complicated and we shall come back to it in
Sections~\ref{sec:ell-isogeny-graphs} and~\ref{sec:sqisign}.

\begin{example}
  \label{ex:1728}
  The elliptic curve $y^2=x^3+x$ has supersingular reduction at all
  primes $p=3\bmod 4$. %
  Its ring of $\F_p$-rational endomorphisms is generated by
  $π=\sqrt{-p}$, and it is not maximal in $ℚ(\sqrt{-p})$.

  The automorphism $ι:(x,y)↦(-x,iy)$ is only defined over $\F_{p^2}$,
  and anti-commutes with $π$. %
  The full endomorphism ring is isomorphic to the maximal order inside
  $B_{p,∞}$ containing both $π$ and $ι$.
\end{example}

\section*{Exercises}

\begin{exercise}
  Prove Proposition~\ref{th:j}.
\end{exercise}

\begin{exercise}
  Determine all the possible automorphisms of elliptic curves.
\end{exercise}

\begin{exercise}
  Prove Proposition~\ref{th:frob}.
\end{exercise}

\begin{exercise}
  Using Proposition~\ref{th:weil}, devise an algorithm to effectively
  compute $\#E(\F_{q^n})$ given $\#E(\F_q)$.
\end{exercise}

\begin{exercise}
  Prove Corollary~\ref{coro:isog-basic}.
\end{exercise}

\begin{exercise}
  Prove Proposition~\ref{prop:weil-det}.
\end{exercise}

\begin{exercise}
  Prove Corollary~\ref{coro:iso-pairing}.
\end{exercise}

\begin{exercise}
  Let $K$ be a complex imaginary number field, $Λ⊂K$ a complex
  lattice, and $\O_Λ$ its order as defined in
  Eq.~\eqref{eq:lattice-order}. %
  Prove that $\O_Λ$ is an order of $K$.
\end{exercise}


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

\clearpage
\part{Isogeny graphs}
\label{part:isogeny-graphs}

We now look at isogeny graphs: graphs with isomorphisms classes of
elliptic curves for vertices, and isogenies for edges. %
Depending on the constraints we put on the isogenies, we will get
graphs with different properties. %
In this part we will study \emph{isogeny volcanoes} and \emph{CM graphs},
whereas Part~\ref{part:ssingular} will be devoted to
\emph{supersingular graphs}.

The classification of isogeny graphs was initiated by
Mestre~\cite{mestre86}, Pizer~\cite{pizer1,pizer2} and
Kohel~\cite{kohel}; further algorithmic treatment of graphs of
ordinary curves, and the now famous name of \emph{isogeny volcanoes},
was subsequently given by Fouquet and
Morain~\cite{fouquet+morain02}. %


\section{Isogeny classes}

We have previously learned that being isogenous is an equivalence
relation,%
\footnote{Reflexivity and transitivity are obvious, symmetry is
  guaranteed by the dual isogeny theorem.} %
it thus makes sense to speak of the \emph{isogeny class} of an elliptic
curve. %
Here, we are interested in characterizing these isogeny classes and
their connectivity structure. %
We will mostly focus on isogeny classes over finite fields, however we
will occasionally mention the complex case.

We start by linking isogeny classes to endomorphism rings.

\begin{theorem}[Serre-Tate]
  \label{th:serre-tate}
  Two elliptic curves $E,E'$ with complex multiplication are isogenous
  (over the algebraic closure) if and only if their \emph{endomorphism
    algebras} $\End(E)⊗ℚ$ and $\End(E')⊗ℚ$ are isomorphic.
\end{theorem}

In layman terms, this theorem is telling us that two curves with
complex multiplication by $\O$ and $\O'$ respectively are isogenous
if and only if $\O⊂\O'$ or $\O'⊂\O$; or equivalently if and only if
$\O$ and $\O'$ have the same field of fractions.

For supersingular curves, we learned that there exists a unique
possibility for $\End(E)⊗ℚ$, namely the unique quaternion algebra
ramified at $p$ and $∞$. %
Then, a similar statement to the complex multiplication case holds.

\begin{theorem}
  \label{th:ssingular-serre-tate}
  Any two supersingular curves over a field of characteristic $p$ are
  isogenous (over the algebraic closure).
\end{theorem}

In the case of finite fields, we saw that $\End(E)⊗ℚ$ is entirely
determined by the Frobenius endomorphism. %
We can strengthen the previous theorems as follows.

\begin{proposition}
  \label{coro:serre-tate}
  Two elliptic curves $E,E'$ defined over a finite field $k$ are
  isogenous over $k$ if and only if $\#E(k)=\#E'(k)$.
\end{proposition}
% todo: check whether rationality really follows from Serre-Tate

At this stage, we are only interested in elliptic curves up to
isomorphism, i.e., $j$-invariants. %
Accordingly, we say that two $j$-invariants are \emph{isogenous}
whenever their corresponding curves are.%
\footnote{In some cases we will be interested in elliptic curves up to
  $k$-rational isomorphisms, and we will then need finer invariants to
  classify them. %
  Likewise, we will say the invariants are isogenous when the
  corresponding curves are.}


\section{Graphs}
\label{sec:graphs}

We recall some basic concepts about graphs and their spectra. %
For a comprehensive treatment,
see~\cite{trevisan-graphs,tao2011expander,Goldreich2011}.

\begin{definition}[Multigraph]
  A \emph{directed multigraph} (or \emph{multidigraph} or \emph{quiver})
  $G$ is a pair $(V,E)$ where $V$ is a set of \emph{vertices} and
  $E∈ℕ^{V×V}$ is a multiset of ordered pairs called \emph{edges}.   
\end{definition}

When $E$ is a simple set, i.e.\ $E∈\{0,1\}^{V×V}$, we recover the
usual definition of a directed graph. %

The \emph{neighbors} of a vertex $v$ are the vertices of $V$ connected
to it by an edge. %
A \emph{path} from a vertex $v$ to another vertex $v'$ is a sequence
of vertices $v\to v_1\to\cdots\to v'$ such that any two consecutive
vertices are neighbors. %
The \emph{distance} from $v$ to $v'$ is the length of the shortest
path between them; if there is no such path, $v'$ is said to be at
infinite distance from $v$. %
The \emph{degree} of a vertex is the number of edges departing from
it; a multigraph where every edge has degree $k$ is called
\emph{$k$-regular}. %
The \emph{adjacency matrix} of a finite multigraph $G=(V,E)$ is the
$|V|×|V|$ matrix with columns and rows indexed by the vertices, where
the $(i,j)$-th entry is the multiplicity of the edge $(v,v')$.

\begin{definition}[Undirected multigraph]
  A multigraph $(V,E)$ is \emph{undirected} if $E(v,v') = E(v',v)$ for
  any $v,v'∈V$, i.e.\ if there are as many edges from $v$ to $v'$ as
  there are from $v'$ to $v$.
\end{definition}

A weakly undirected multigraph is called \emph{connected} if any two
vertices have a path connecting them; it is called \emph{disconnected}
otherwise. %
A \emph{connected component} of an undirected multigraph is a maximal
subgraph (i.e.\ a subset $V'⊂V$ together with the restriction of $E$
to $V'$) that is connected. %
The \emph{diameter} of a connected multigraph is the largest of all
distances between its vertices. %

\begin{definition}[Spectrum]
  The \emph{spectrum} of a finite multigraph is the multiset of the
  eigenvalues of its adjacency matrix.
\end{definition}

When the multigraph is undirected, the adjacency matrix is symmetric,
thus its spectrum is real. %
Let $(V,E)$ be $k$-regular and undirected, and let $V'⊂V$ be the set
of vertices of a connected component. %
It is easy to see that the vector having $1$'s for the entries
corresponding to $V'$ and $0$'s elsewhere is an eigenvector with
eigenvalue $k$. %
We can in fact prove a stronger statement.

\begin{theorem}
  Let $G$ be a $k$-regular undirected multigraph and let
  $λ_1 ≥ λ_2 ≥ \cdots ≥ λ_n$ be its spectrum. %
  Then $|λ_i| ≤ k$, and the multiplicity of the eigenvalue $k$ equals
  the number of connected components of $G$.
\end{theorem}
\begin{proof}
  See~\cite[Chap.~3]{trevisan-graphs}.
\end{proof}

\emph{Expansion} is a way to express how ``well connected'' the nodes
of a graph are. %
There are several related definitions of it. %
We start with the spectral definition, which is simpler to state and
often easier to prove, but whose implications are less obvious. %
From now on, whenever we have a multigraph, we denote by
$λ_1 ≥ λ_2 ≥ \cdots ≥ λ_n$ its spectrum.

\begin{definition}[Expander graph]
  Let $ε>0$ and $k≥1$. %
  A $k$-regular undirected multigraph 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 multigraphs 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}

Ramanujan proved a bound on how large $ε$ can be in an expander
family. %

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

Another way to characterize expansion is \emph{edge expansion}, which
quantifies how well subsets of vertices are connected to the whole
graph, or, said otherwise, how far the graph is from being
disconnected.

\begin{definition}[Edge expansion]
  Let $F⊂V$ be a subset of the vertices of $G$. %
  The \emph{boundary of $F$}, denoted by $∂F⊂E$, is the subset of the
  edges of $G$ that go from $F$ to $V\setminus F$. %
  The \emph{edge expansion ratio} of $G$, denoted by $h(G)$ is the
  quantity
  \[h(G) = \min_{\substack{F⊂V,\\ \#F≤\#V/2}}\frac{\#∂F}{\#F}.\]
\end{definition}

Note that $h(G)=0$ if and only if $G$ is disconnected. %
Edge expansion is strongly tied to spectral expansion, as the
following theorem shows.

\begin{theorem}[Discrete Cheeger inequality]
  Let $G$ be a $k$-regular one-sided $ε$-expander, then
  \[\frac{ε}{2}k≤h(G)≤\sqrt{2ε}k.\]
\end{theorem}

Expander families of multigraphs have many applications in theoretical
computer science, thanks to their \emph{pseudo-randomness} properties:
they are useful to construct \emph{pseudo-random number generators},
\emph{error-correcting codes}, \emph{probabilistic checkable proofs},
and, as we shall see, \emph{cryptographic protocols}. %
Among their properties, they have \emph{short diameter} and
\emph{rapidly mixing walks}.

\begin{proposition}
  \label{th:diameter}
  Let $G$ be a $k$-regular one sided $ε$-expander. %
  For any vertex $v$ and any radius $r>0$, let $B(v,r)$ be the
  \emph{ball} of vertices at distance at most $r$ from $v$. %
  Then, there is a constant $c>0$, depending only on $k$ and $ε$, such
  that
  \[\#B(v,r)≥\min((1+c)^r,\#V).\]
\end{proposition}

In particular, this shows that the diameter of an expander is bounded
by $O(\log n)$, where the constant depends only on $k$ and $ε$. %

A \emph{random walk} of length $m$ is a path $v_1\to\cdots\to v_m$,
defined by the random process that selects $v_i$ uniformly at random
among the neighbors of $v_{i-1}$. %
If we start from some probability distribution $\mathbf{p}$ on $V$ and
walk randomly for $m$ steps, the final vertex of the walk will be
distributed like $(A/k)^m\mathbf{p}$, where $A$ is the adjacency matrix of
the graph. %
The following theorem tells us that, for two-sided expanders, this
distribution converges exponentially fast in $m$ to the uniform
distribution.

\begin{proposition}[Mixing theorem]
  \label{th:mixing}
  Let $G=(V,E)$ be an undirected $k$-regular multigraph, let $A$ be
  its adjacency matrix, and let $σ₂ = \max(|λ_2|, |λ_n|)$.  %
  Then for every distribution $\mathbf{p}$ on $V$ and every $m>0$, we
  have
  \begin{equation*}
    \| \mathbf{u} - (A/k)^m \mathbf{p} \|_1 ≤ \sqrt{n} \left(\frac{σ_2}{k}\right)^m,
  \end{equation*}
  where $\mathbf{u}$ denotes the uniform distribution on $V$.
\end{proposition}
\begin{proof}
  See~\cite[Chap.~21]{trevisan-graphs}.
\end{proof}

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,trevisan-graphs}. %
In this part we will encounter a construction based on isogenies which
is essentially a Cayley graph. %
In Part~\ref{part:ssingular} we will introduce a different
construction which achieves Ramanujan's bound.

\begin{definition}[Isogeny graph]
  An \emph{isogeny graph} is a multigraph whose vertices are
  isomorphism classes of isogenous curves, and whose edges are
  isogenies between them.
\end{definition}


\begin{figure}
  \centering
    \begin{tikzpicture}
      \begin{scope}[xshift=6cm]
        \def\crater{7}
        \foreach \i in {1,...,\crater} {
          \draw[fill] (360/\crater*\i:1cm) circle (5pt);
          \draw (360/\crater*\i : 1cm) -- (360/\crater*\i+360/\crater : 1cm);
          \foreach \j in {-1,1} {
            \draw[fill] (360/\crater*\i : 1cm) -- (360/\crater*\i + \j*360/\crater/4 : 2cm) circle (3pt);
            \foreach \k in {-1,0,1} {
              \draw[fill] (360/\crater*\i + \j*360/\crater/4 : 2cm) --
              (360/\crater*\i + + \j*360/\crater/4 + \k*360/\crater/6 : 2.5cm) circle (1pt);
            }
          }
        }
      \end{scope}
      \begin{scope}[xshift=12cm]
        \node at (0,2) {$\End(E)$};
        \draw[fill] (0,1) circle(5pt) node[xshift=0.7cm]{$\O_K$} -- 
        (0,0) circle(3pt) --
        (0,-1) circle(1pt) node[xshift=0.7cm]{$ℤ[π]$};
      \end{scope}
    \end{tikzpicture}
  
    \caption{A volcano of $3$-isogenies (ordinary elliptic curves,
      Elkies case), and the corresponding tower of orders inside the
      endomorphism algebra.}
  \label{fig:volcano}
\end{figure}

Whenever we include an isogeny in an isogeny graph we will always
include its dual too, thus we will usually draw the (multi)graphs as
undirected. %
Figure~\ref{fig:volcano} shows a typical example of isogeny graph over
a finite field, where we restrict to isogenies of degree $3$. %

Note, however that there is an asymmetry in this definition: because
we take isogenies up to composition with isomorphisms on the right,
several distinct isogenies may have the same dual.%
\footnote{This can only happen when the automorphism groups of two
  connected vertices have different sizes, and can thus only happen at
  a finite number of vertices.} %
This means that isogeny graphs are not undirected in the sense
previously defined, however they will behave as such for most
practical purposes. %


\section{Isogeny volcanoes}
\label{sec:ell-isogeny-graphs}

When we restrict to isogenies of a prescribed prime degree $ℓ$, we say
that two curves are $ℓ$-isogenous; by the dual isogeny theorem, this
is a symmetric relation. %
Remark that being $ℓ$-isogenous is also well defined up to
isomorphism.

Let us start with the local structure of the graph: given an elliptic
curve $E$ and a prime $ℓ$, how many isogenies of degree $ℓ$ have $E$
as domain? %
Thanks to Proposition~\ref{prop:isoker}, we know this is equivalent to
asking how many subgroups of order $ℓ$ the curve has; but then we
immediately know there are exactly $ℓ+1$ isogenies whenever $ℓ≠p$.

For our first example, let us consider a curve $E/ℂ$ \emph{without}
complex multiplication, i.e., such that $\End(E)=ℤ$.  %
Its $ℓ$-isogeny graph, i.e., the connected component of the graph of
$ℓ$-isogenies containing $E$, is $(ℓ+1)$-regular, and cannot have
loops, otherwise that would provide a non-trivial cyclic endomorphism of $E$
of degree a power of $ℓ$. %
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 over $ℂ$
      without complex multiplication.}
  \label{fig:infinite-tree}
\end{figure}

When we think about curves over finite fields, however, some of the
isogenies may only be defined in the algebraic closure, thus we would
like to restrict our graphs to those isogenies that are defined over
$\F_q$. %
Fortunately, we have a Swiss-army-knife to address this question: the
\emph{Frobenius endomorphism} $π$. %
Formally, an isogeny $ϕ$ is $\F_q$-rational if and only if
$π(\ker ϕ)=\ker ϕ$, 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. %
If $n$ is the smallest exponent such that $π^n$ acts like a scalar
multiplication, i.e.\ if $n$ is the order of $π$ in $\PGL_2(\F_ℓ)$,
then $\F_{q^n}$ is the smallest field 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}. See
  Appendix~\ref{sec:appl-point-count}.}:
\begin{itemize}
\item[(0)] $π$ is not triangularizable over $\F_ℓ$, then it has no
  eigenvalues and $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 its characteristic polynomial $x^2-tx+q$ over $\F_ℓ$,
or equivalently on whether $Δ_π=t^2-4q$ is a square modulo $ℓ$. %

But what about the global structure of the graph? %
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 Figure~\ref{fig:infinite-tree} must somehow
``fold'' or ``be pruned'' to fit inside $\F_q$. %

For example, if $E/\F_q$ is a supersingular curve, we shall see later
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, Kohel~\cite{kohel} introduced a
notion of ``depth'' in the graph. %
Let $E/\F_q$ have complex multiplication by an order $\O$ in a number
field $K=ℚ(π)$. %
Write $\O_K$ for the maximal order of $K$, then we know that
$ℤ[π] ⊂ \O ⊂ \O_K$. %
We have already seen that two elliptic curves are isogenous if and
only if they have the same endomorphism algebra $K$; Kohel refined
this statement 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 rings. %
  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?  %
The following theorem gives a complete classification, also 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{proof}
  See~\cite[Prop.~21]{kohel}, or~\cite[Lecture~23]{sutherland-notes}.
\end{proof}

\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. %
  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}. %
Their looks have justified the name of \emph{isogeny volcanoes} for
them~\cite{fouquet+morain02}; in the Elkies case, we call
\emph{crater} the cycle at the surface.

We are left with one last question: how large are these graphs? %
To address this question, we shall need the theory of complex
multiplication.

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

We now introduce a powerful tool for the study of isogeny graphs. %
Our goal is to characterize elliptic curves with complex
multiplication; to do so, we start from elliptic curves defined over
the complex numbers. %

Let $K$ be a quadratic imaginary field and let $Λ$ be a complex
lattice such that $Λ⊂K$. %
Recall that the order $\O_Λ$ of $Λ$ is the ring
\begin{equation}
  \label{eq:lattice-order}
  \O_Λ = \{ α ∈ K \;\mid\; αΛ ⊂ Λ \},
\end{equation}
i.e.\ $Λ$ is a fractional $\O_Λ$-ideal. %
Using Theorem~\ref{th:weierstrass-p} we associate to $Λ$ a complex
elliptic curve $E_Λ$; but then, by definition, $\O_Λ≃\End(E_Λ)$. %
Said otherwise, $E_Λ$ has \emph{complex multiplication} by $\O_Λ$.

We have thus found a way to construct elliptic curves over the complex
numbers with complex multiplication by a specified order. %
Conversely, every curve with complex multiplication arises this way. %
To show this, we look at the set of all isomorphism classes of
elliptic curves with complex multiplication by a specified order $\O$,
which we will denote by $\Ell(\O)$. %
Because homothetic lattices give rise to isomorphic curves, fractional
ideals $\a$ and $c\a$ will be associated to isomorphic curves $E_\a$
and $E_{c\a}$ as long as $c≠0$. %
This justifies looking at fractional ideals modulo principal ideals.

\begin{definition}[Ideal class group]
  Let $\O$ be an order of a number field $K$. %
  Let $\mathcal{I}(\O)$ be the group of invertible fractional
  $\O$-ideals, and let $\mathcal{P}(\O)$ be the group of principal
  ideals. %

  The \emph{ideal class group} of $\O$ is the quotient group
  \[\Cl(\O) = \mathcal{I}(\O)/\mathcal{P}(\O).\]
  It is a finite Abelian group; its order is called the \emph{class
    number} of $\O$, and denoted by $h(\O)$.
\end{definition}

When $\O$ is the maximal order, $\Cl(\O)$ is also called the class
group of $K$. %
The class group is a fundamental object in \emph{class field theory}:
when $\O$ is the maximal order of an imaginary quadratic number field
$K$, it is isomorphic to the Galois group
of the maximal unramified Abelian extension of $K$, also called the
\emph{Hilbert class field} of $K$; more generally, non-maximal orders
are connected to ramified Abelian extensions of $K$. %
The next theorem highlights a fundamental connection between the class
group and the modular $j$-invariant, and thus to elliptic curves with
complex multiplication by $\O$.

\begin{theorem}
  \label{th:compl-mult}
  Let $\O$ be an order of an imaginary quadratic
  number field $K$, and let
  $\a_1,\dots,\a_{h(\O)}$ be representatives of $\Cl(\O)$. %
  Then:
  \begin{itemize}
  \item $K(j(\a_i))$ is an Abelian extension of $K$;
  \item The $j(\a_i)$ are all conjugate over $K$;
  \item The Galois group of $K(j(\a_i))$ is isomorphic to $\Cl(\O)$;
  \item $[ℚ(j(\a_i)):ℚ] = [K(j(\a_i)):K] = h(\O)$;
  \item The $j(\a_i)$ are integral, their minimal polynomial is called
    the \emph{Hilbert class polynomial} of $\O$;
  \item $\Cl(\O)$ acts freely and transitively on $\Ell(\O)$, in
    particular $\#\Ell(\O) = h(\O)$.
  \end{itemize}
\end{theorem}
\begin{proof}
  See~\cite[Ch.~II]{silverman:advanced} and~\cite[Ch.~10]{lang1987elliptic}.
\end{proof}

Hence, we have completely characterized all elliptic curves with
complex multiplication by an order $\O$, up to isomorphism; in
particular, we now know that $j$-invariants with complex
multiplication (sometimes called \emph{singular $j$-invariants}) are
algebraic integers. %
In the next section, we shall say more on how $\Cl(\O)$ acts on the set
$\Ell(\O)$.

\begin{example}
  Let $\O=ℤ[i]$, so that $\O$ is the ring of integers of $ℚ(i)$. %
  It was already proven by Gauss that $ℤ[i]$ is a principal ideal
  domain, and thus that its class group is trivial. %
  Up to homothety, there is a unique lattice with order $ℤ[i]$, and
  one such representative is $ℤ[i]$ itself.

  Recall the definition of the Eisenstein series
  \[G_{2k}(Λ) = \sum_{ω∈Λ\setminus\{0\}} ω^{-2k}.\]
  But in our case $Λ=ℤ[i]$, thus $iΛ=Λ$, hence
  \[G_{2k}(Λ) = G_{2k}(iΛ) = i^{-2k}G_{2k}(Λ) = (-1)^kG_{2k}(Λ).\] In
  particular $G_6(Λ) = - G_6(Λ) = 0$, hence, by the definition of the
  modular $j$-invariant (Theorem~\ref{th:modular-j}),
  $j(ℤ[i]) = 1728$.

  This shows that that the Hilbert class polynomial of $ℤ[i]$ is
  $X-1728$, and that the curve $E\;:\;y^2=x^3+x$ is the only curve
  over $ℂ$, up to isomorphism, with complex multiplication by
  $ℤ[i]$. %
  In particular, $ℤ[i]$ contains a subgroup of units $\{±1,±i\}$,
  which correspond to the four automorphisms generated by the map
  \begin{align*}
    ι : E &→ E,\\
    (x,y) &↦ (-x,iy).
  \end{align*}
\end{example}


\subsection{Complex multiplication for finite fields}
At this point, we have a complete characterization of complex
multiplication elliptic curves in characteristic $0$. %
What happens, then, in positive characteristic $p$? %

There are at least two ways in which we could construct elliptic
curves over a finite field with endomorphism ring larger than $ℤ$. %
One is to start from a complex multiplication elliptic curve $E$
defined over a number field $L$, and then reduce at a place\footnote{A
  \emph{place} is just a fancy name for a prime ideal of $L$.}
$\frak{p}$ over $p$. %
We write $\bar{E} = E(\frak{p})$ for the reduction of $E$ at the place
$\frak{p}$; if we do this carefully (for example, we must avoid
singular reductions), non-trivial endomorphisms of $E$ will descend to
non-trivial endomorphisms of $\bar{E}$. %

\begin{theorem}[Deuring]
  \label{th:deuring-red}
  Let $E$ be an elliptic curve over a number field $L$, with complex
  multiplication by an order $\O⊂K$. %
  Let $\frak{p}$ be a place of $L$ over $p$, and assume that $E$
  has non-singular reduction $\bar{E}$ modulo $\frak{p}$. %
  The curve $\bar{E}$ is supersingular if and only if $p$ has only one
  prime of $K$ above it ($p$ fully ramifies or remains prime in $k$).

  Suppose that $p$ splits completely in $K$. %
  Let $f$ be the conductor of $\O$, and write $f = p^rf_0$, where
  $p\nmid f_0$. %
  Then:
  \begin{itemize}
  \item $\bar{E}$ has complex multiplication by the order in $K$ with
    conductor $f_0$.
  \item If $p\nmid f$, then the map $ω↦\omega(\frak{p})$ defines an
    isomorphism of $\End(E)$ and $\End(\bar{E})$.
  \end{itemize}
\end{theorem}
\begin{proof}
  See~\cite[Ch.~13]{lang1987elliptic}.
\end{proof}

Note that $p>2$ splits in $K$ if and only if the fundamental
discriminant $Δ_K$ of $K$ is a square modulo $p$, i.e.\ if the
Legendre symbol $\left(\frac{Δ_K}{p}\right)$ is equal to $1$. %
To cover the case $p=2$ with the same notation, we may use Kronecker's
extension of Legendre's symbol, which is equal to $1$ if and only if
$p$ splits. %

\begin{example}
  We have seen that the elliptic curve $E/ℚ$ defined by $y^2=x^3+x$
  has complex multiplication by $ℤ[i]$. %
  Assume $p>2$; by virtue of the theorem above, $E(p)$ is
  supersingular if and only if $(-4/p)=-1$, i.e., if and only if
  $p≡3 \bmod 4$.

  In particular, this implies that $-1$ is not a square modulo $p$,
  and thus that the automorphism $(x,y)↦(-x,iy)$ does not descend to
  an $\F_p$-automorphism of $E(p)$. %
  It does, however, descend to an $\F_{p^2}$-automorphism, showing
  that $\End(E(p))$ contains is not commutative, but contains a
  subring isomorphic to $ℤ[i]$.
\end{example}

Another approach is to directly construct a curve $E/\F_q$ so that its
Frobenius endomorphism is in the desired order. %
Recall that the Frobenius endomorphism $π$ satisfies a quadratic
equation
\[π^2 - tπ + q = 0,\] %
with discriminant $Δ_π=t^2-4q≤0$. %
Setting the case $Δ_π=0$ aside, $\End(E)$ necessarily contains a
subring $ℤ[π]$, isomorphic to an order of $ℚ(\sqrt{Δ_π})$. %
It turns out that these approach is essentially equivalent to the
previous one, as a famous theorem shows.

\begin{theorem}[Deuring's lifting theorem]
  \label{th:deuring-lift}
  Let $E_0$ be an elliptic curve in characteristic $p$, with an
  endomorphism $ω_o$ which is not trivial. %
  Then there exists an elliptic curve $E$ defined over a number field
  $L$, an endomorphism $ω$ of $E$, and a non-singular reduction of $E$
  at a place $\frak{p}$ of $L$ lying above $p$, such that $E_0$ is
  isomorphic to $E(\frak{p})$, and $ω_0$ corresponds to $ω(\frak{p})$
  under the isomorphism.
\end{theorem}
\begin{proof}
  See~\cite[Ch.~13]{lang1987elliptic}.
\end{proof}


\section{Isogenies and the CM action}
\label{sec:compl-mult-2}

From now on we abbreviate ``complex multiplication'' by CM. %
We saw in Theorem~\ref{th:compl-mult} that the class group $\Cl(\O)$
acts on the set $\Ell(\O)$ of CM elliptic curves over $ℂ$ with complex
multiplication by $\O$. %
After having identified $\Cl(\O)$ with the Galois group of the Hilbert
class field, this action is just the Galois action, however we are
still missing an explicit identification. %

Additionally, when working with CM curves over a finite field, it
becomes clumsy (and even computationally infeasible) to go back to $ℂ$
in order to identify the curves with the generators of the Hilbert
class field and then act on them by Galois. %
Instead, we will now give the action of $\Cl(\O)$ on $\Ell(\O)$
explicitly, without any mention of class field theory. %

From now on we let $\O$ be an order in a number field $K$, we denote
by $\Ell_q(\O)$ the set of elliptic curves over $\F_q$ with CM by
$\O$, and we assume that it is non-empty. %
Because curves in $\Ell_q(\O)$ are connected exclusively by horizontal
isogenies, we will also call it a \emph{horizontal isogeny class}.

Let $E∈\Ell_q(\O)$, let $\a$ be an invertible ideal in $\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.%
\footnote{A more formal treatment encompassing inseparable isogenies will be given in Section~\ref{sec:quat-mult-aka}.}

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)$. %
Since the action factors through principal ideals, 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]
  \label{th:compl-mul}
  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 (also called a \emph{torsor})
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}
\]
This confirms what we already knew, that $\#\Ell_q(\O)=h(\O)$. %
We summarize in Table~\ref{tab:cm} the correspondence between ideals
and isogenies given by complex multiplication. %
We now have all the necessary element to answer our original question
on the size of $ℓ$-isogeny volcanoes.

\begin{table}
  \centering
  \begin{tabular}{l@{\hspace{5em}}l}
    \bf Number fields & \bf Elliptic curves\\
    \hline
    Order & Endomorphism ring\\
    Integral invertible ideal & Horizontal isogeny\\
    Integral principal ideal & Endomorphism\\
    Conjugate ideal & Dual isogeny\\
    Ideal norm & Isogeny degree\\
    Ideal class & $\Hom(E,E')$\\
  \end{tabular}
  \caption{Correspondences of complex multiplication.}
  \label{tab:cm}
\end{table}

\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}

But we can extract even more information from the group action. %
Assume that the Frobenius endomorphism splits modulo $ℓ$, i.e., that
\[π^2 - tπ + q = (π - λ)(π - μ) \mod\ell\] %
for two distinct eigenvalues $λ,μ$ of the action of $π$ on $E[ℓ]$. %
Associate to $λ$ and $μ$ the prime ideals $\a=(π-λ,ℓ)$ and
$\hat{\a}=(π-μ,ℓ)$, both of norm $ℓ$; then $E[\a]⊂E[ℓ]$ is the
eigenspace of $λ$, and $E[\hat{\a}]⊂E[ℓ]$ 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). %

Hence, we see 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. %
What we have here is a very basic example of \emph{Cayley graph}.

\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}


\begin{definition}[Cayley graph]
  \label{def:cayley}
  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}

The graph in Figure~\ref{fig:cycle} is isomorphic to a Cayley graph of
$\Cl(\O)$ for an edge set $S=\{\a,\hat\a\}$, but, unlike the Cayley
graph itself, its vertex set is $\Ell_q(\O)$, which is in bijection
with $\Cl(\O)$ only up to automorphism.%
\footnote{Said otherwise, any vertex could be mapped to the identity
  of $\Cl(\O)$, and ``we forgot which one it was''.} %
This graph is sometimes called the \emph{Schreier graph} of
$(\Cl(\O),S,\Ell_q(\O))$, to distinguish it from the proper Cayley
graph.

Is this graph, a cycle when seen as an undirected 2-regular graph, an
expander? %
By properly arranging vertices, its adjacency matrix is circulant with
two non-zero entries per row, hence its eigenvalues are
$\lambda_t = e^{2iπt/n} + e^{-2iπt/n}$ for $t=0,\dots,n-1$ where
$n=h(\O)$. %
In particular $λ_0=2$, and $λ_1→2$ as $n→∞$, proving that cycles are
not expanders; and indeed, it is obvious that this graph has large
diameter relative to the number of vertices, contradicting
Proposition~\ref{th:diameter}.

It turns out that we can obtain expanders in this way by ``gluing many
isogeny craters together'', as represented in Figure~\ref{fig:cayley},
by taking just a slightly larger set $S⊂\Cl(\O)$. %
The following theorem is an instance of a classic technique to
construct expanders from Cayley graphs
(see~\cite[Chap.~16]{trevisan-graphs}).

\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}


\section*{Exercises}

\begin{exercise}
  Prove that Proposition~\ref{coro:serre-tate} implies the finite
  field case of Theorems~\ref{th:serre-tate}
  and~\ref{th:ssingular-serre-tate}. %
  Then, prove the converse.
\end{exercise}

\begin{exercise}
  Prove that the dual of a horizontal isogeny is horizontal, and that
  the dual of a descending isogeny is ascending.
\end{exercise}

\begin{exercise}
  Prove that the height of a volcano of $ℓ$-isogenies is $v_ℓ(f_π)$,
  the $ℓ$-adic valuation of the Frobenius endomorphism.
\end{exercise}

\begin{exercise}
  Let $X^2-tX-q$ be the minimal polynomial of $π$, and suppose that it
  splits as $(X-λ)(X-μ)$ in $ℤ_ℓ$ (the ring of $ℓ$-adic integers). %
  Prove that the volcano of $ℓ$-isogenies has height $v_ℓ(λ-μ)$.
\end{exercise}

\begin{exercise}
  \label{ex:group-struct}
  Prove that $E[ℓ]⊂E(\F_q)$ implies $ℓ|(q-1)$.
\end{exercise}

\begin{exercise}
  Let $ω∈ℂ$ be a cube root of unity, the ring $ℤ[ω]$ is also known as
  the \emph{Eisenstein integers}. %
  Determine all elliptic curves with complex multiplication by $ℤ[ω]$.
\end{exercise}

\begin{exercise}
  Prove that $-163$ is not a square modulo all odd primes
  $<41$. (Hint: $ℚ(\sqrt{-163})$ has class number $1$).
\end{exercise}

\begin{exercise}
  Find a prime power $q$ and an elliptic curve $E/\F_q$ such that the
  $3$-isogeny volcano of $E$ is the same as the one in
  Figure~\ref{fig:volcano}.
\end{exercise}


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

\clearpage
\part{Cryptographic group actions}
\label{part:crypt-group-acti}

In this part we introduce our first isogeny based cryptographic
protocols. %
We start with the classic elliptic curve Diffie--Hellman key exchange
(ECDH), then we introduce a generalization of Diffie--Hellman based on
the theory of complex multiplication and we present a particularly
efficient instantiation named CSIDH. %
Finally we discuss security and rapidly survey other schemes based on
complex multiplication.


\section{Diffie--Hellman key exhange}
\label{sec:appl-diff-hellm}

Elliptic curves are largely present in modern technology thanks to
their applications in cryptography. %
The simplest of these applications is the \emph{Diffie--Hellman key
  exchange}, a cryptographic protocol by which two parties
communicating over a public channel can agree on a common secret
string unknown to any other party listening on the same channel.

The original protocol was invented in the 1970s by Whitfield Diffie
and Martin Hellman~\cite{DifHel76}, and constitutes the first practical
example of \emph{public key cryptography}. %
The two communicating parties are customarily called \emph{Alice} and
\emph{Bob}, and the snooping third party is represented by the
character \emph{Eve} (for \emph{eavesdropper}). %
To set up the protocol, Alice and Bob agree on a set of public
parameters:
\begin{itemize}
\item A \emph{large enough} prime number $p$, such that $p-1$ has a
  \emph{large enough} prime factor;
\item A multiplicative generator $g∈ℤ/pℤ$.
\end{itemize}

Then, Alice and Bob perform the following steps:
\begin{enumerate}
\item Each chooses a \emph{secret} integer in the interval $]0,p-1[$;
  call $a$ \emph{Alice's secret} and $b$ \emph{Bob's secret}.
\item They respectively compute $A=g^a$ and $B=g^b$.
\item They exchange $A$ and $B$ over the public channel.
\item They respectively compute the \emph{shared secret}
  $B^a=A^b=g^{ab}$.
\end{enumerate}

The protocol can be easily generalized by replacing the multiplicative
group $(ℤ/pℤ)^{×}$ with any other cyclic group $G=〈g〉$. %
From Eve's point of view, she is given the knowledge of the group $G$,
the generator $g$, and Alice's and Bob's public data $A,B∈G$; her goal
is to recover the shared secret $g^{ab}$. %
This is known as the \emph{Computational Diffie--Hellman} (CDH)
problem. %
An even simpler problem is the following.

\begin{definition}[Discrete logarithm]
  Let $G$ be a cyclic group generated by an element $g$. For any
  element $A∈G$, we define the \emph{discrete logarithm of $A$ in base
    $g$}, denoted $\log_g(A)$, as the unique integer in the interval
  $[0,\#G[$ such that
  \[g^{\log_g(A)} = A.\]
\end{definition}

It is clear that if Eve can compute discrete logarithms in $G$
efficiently, then she can solve CDH. %
The converse is not true in general, but it is generally assumed to
be. %
At any rate, the best attacks against CDH use a discrete logarithm
solver, this is why we usually say that the Diffie--Hellman protocol
is based on the hardness of the discrete logarithm problem in the
group $G$.

We know algorithms to compute discrete logarithms in a \emph{generic}
group $G$ that require $O(\sqrt{q})$ computational steps
(see~\cite{joux2009algorithmic}), where $q$ is the largest prime
divisor of $\#G$; we also know that these algorithms are \emph{optimal
  for abstract cyclic groups}~\cite{EC:Shoup97}. %
For this reason, $G$ is usually chosen so that the largest prime
divisor $q$ has size at least $\log_2 q ≈ 256$. %
However, the proof of optimality does not exclude the existence of
better algorithms for \emph{specific} groups $G$. %
And indeed, algorithms of complexity better than $O(\sqrt{\#G})$ are
known for the case $G=(ℤ/pℤ)^{×}$~\cite{joux2009algorithmic}, thus
requiring parameters of considerably larger size to guarantee
cryptographic strength.

On the contrary, no algorithms better than the generic ones are known
when $G$ is a subgroup of $E(k)$, where $E$ is an elliptic curve
defined over a finite field $k$. %
This led Miller~\cite{C:Miller85} and
Koblitz~\cite{koblitz87,JC:Koblitz89} to suggest, in the 1980s, to
replace $(ℤ/pℤ)^{×}$ in the Diffie--Helman protocol by the group of
rational points of an elliptic curve of (almost) prime order over a
finite field. %
The resulting protocol is summarized in Figure~\ref{fig:dh}.

\begin{figure}
  \centering
  \begin{tabular}{l *{2}{p{25ex}<{\centering}}}
    \hline
    Public parameters & \multicolumn{2}{l}{Finite field $\F_p$, with $\log_2p≈256$,}\\
                      & \multicolumn{2}{l}{Elliptic curve $E/\F_p$, such that $\#E(\F_p)$ is prime,}\\
                      & \multicolumn{2}{l}{A generator $P$ of $E(\F_p)$.}\\
    \hline
                      & {\bf Alice} & {\bf Bob}\\
    \hline
    Pick random secret & $0<a<\#E(\F_p)$ & $0<b<\#E(\F_p)$\\
    Compute public data & $A = [a]P$ & $B = [b]P$\\
    Exchange data &  \hfill $A \longrightarrow$ & $\longleftarrow B$ \hfill\strut \\
    Compute shared secret & $S = [a]B$ & $S = [b]A$
  \end{tabular}
  
  \caption{The Diffie--Hellman protocol over elliptic curves}
  \label{fig:dh}
\end{figure}

The Elliptic Curve Diffie--Hellman protocol (ECDH) is today a widely
adopted standard, used for example to establish secure TLS connection,
the encrypted layer of Internet. %
Other protocols built on top of the difficulty of solving the elliptic
curve discrete logarithm problem, such as the ECDSA signing algorithm,
are also widely in use today.

In recent years, however, there has been a push to amend cryptographic
standards in view of the threat posed by general purpose \emph{quantum
  computers}. %
It is well known, indeed, that Shor's algorithm~\cite{FOCS:Shor94}
would solve the factorization and the discrete logarithm problems in
polynomial time on a quantum computer, thus sealing the fate of RSA,
ECDH, and any other protocol based on them. %

In the next sections we shall present \emph{cryptographic group
  actions}, a generalization of discrete logarithm groups that is
believed to be, in general, resistant to attacks by quantum
computers. %
The only examples of quantum-resistant cryptographic commutative group
actions currently known are based on the theory of complex
multiplication.


\section{Cryptographic group actions}
\label{sec:crypt-group-acti}

In his seminal unpublished work~\cite{EPRINT:Couveignes06}, Couveignes
defined a generalization of discrete logarithm groups called
\emph{hard homogeneous spaces}, a fancy name for a group action with
some associated hard computational problem. %
Group actions had previously been considered by Brassard and
Yung~\cite{C:BraYun90}, although their focus differs slightly from
Couveignes'. %
We shall follow here the more modern treatment of~\cite{AC:ADMP20},
where these are called \emph{cryptographic group actions}.

Below we write $(G,X,·)$ for the action of a group $G$ on a set
$X$, denoted by $x' = g·x$.

\begin{definition}[Effective Group Action]
  A group action $(G,X,·)$ is \emph{effective} if the following
  properties are satisfied:
  \begin{enumerate}
  \item The group $G$ is finite and there exist efficient algorithms
    for:
    \begin{enumerate}
    \item \emph{Membership testing}, i.e., to decide if a given bit string
      represents a valid group element in $G$.
    \item \emph{Equality testing}, i.e., to decide if two bit strings
      represent the same group element in $G$.
    \item \emph{Sampling}, i.e., to sample an element $g$ from a
      distribution on $G$ statistically close to uniform.
    \item \emph{Operation}, i.e., to compute $gh$ for any $g,h\in G$.
    \item \emph{Inversion}, i.e., to compute $g^{-1}$ for any
      $g\in G$.
    \end{enumerate}
  \item The set $X$ is finite and there exist efficient algorithms for:
    \begin{enumerate}
    \item \emph{Membership testing}, i.e., to decide if a bit string
      represents a valid set element.
    \item \emph{Unique representation}, i.e., given any arbitrary set element $x\in X$, compute a string $\hat{x}$ that canonically represents $x$.
    \end{enumerate}
  \item There exists a distinguished element $x_0\in X$, called the
    \emph{origin}, such that its bit-string representation is
    known.\footnote{Like a group generator, the origin does not
      necessarily have a distinguishing mathematical property, and can
      be taken arbitrarily.}
  \item There exists an efficient algorithm that given (some
    bit-string representations of) any $g\in G$ and any $x\in X$,
    outputs $g · x$.
  \end{enumerate}
\end{definition}

In practice, we will mostly deal with regular group actions, i.e.\
such that for any $x, x' ∈ X$ there is a unique $g ∈ G$ such that
$g · x = x'$. %
Then, $\#G = \#X$. %
Additionally, we will only consider Abelian group actions.

\begin{definition}
  Let $(G,X,·)$ be an effective group action. %
  Define the functions
  \begin{equation*}
    \begin{aligned}
      f_x : G &\to X,\\
      g &\mapsto g·x,
    \end{aligned}
    \qquad\qquad
    \begin{aligned}
      \pi_g : X &\to X,\\
      x &\mapsto g·x.
    \end{aligned}
  \end{equation*}
  The group action is said to be:
  \begin{enumerate}
  \item \emph{One-way} if the family of functions $f_x$ is one-way.
  \item \emph{Weakly unpredictable} if the family of permutations
    $\pi_g$ is weakly unpredictable, i.e., if given a list of random
    pairs $(x,\pi_g(x))$ it is hard to guess $\pi_g(x^*)$ for a random
    $x^*$ not in the list.
  \item \emph{Weakly pseudorandom} if the family of permutations
    $\pi_g$ is weakly pseudorandom, i.e., if it is hard to distinguish
    between a list of random pairs $(x,\pi_g(x))$ and one of random
    pairs $(x,\pi(x))$, where $\pi$ is a uniformly drawn permutation
    of $X$.
  \end{enumerate}
\end{definition}

Discrete logarithm groups are special cases of cryptographic group
actions. %
Indeed, if $H$ is a group of order $n$, we let $X⊂H$ be the subset of
elements of order $n$, and we let $G = (ℤ/nℤ)^\times$. %
Then $G$ acts regularly on $X$, and it is easy to check that
one-wayness, weak unpredictability and weak pseudorandomness
correspond to the difficulty of, respectively, discrete logarithm, CDH
and DDH%
\footnote{DDH is the \emph{decisional} variant of CDH: distinguish
  $(g,h,g^a,h^a)$ from a random tuple $(g,h,g^a,h^b)$ of group elements}.

Likewise, we can generalize the Diffie--Hellman key exchange to
cryptographic (Abelian) group actions. %
The system parameters are the effective group action $(G,X,·)$ with
its origin $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, the shared secret is derived as
\begin{equation*}
  g_A·x_B = g_Ag_B· x_0 = g_Bg_A·x_0 = g_B·x_A.
\end{equation*}

Of course, we want to instantiate this protocol with group actions
that are not just a discrete logarithm group in disguise. %
For example, for the group action of complex multiplication, the three
hardness properties correspond to the following three problems.

\begin{problem}[Group action inverse problem, Vectorization]
  \label{prob:gaip}
  Given two elliptic curves $E,E'$ with complex multiplication by an
  order $\O$, find an ideal (class) $\frak a⊂\O$ such that
  $E'=\frak a · E$.
\end{problem}

\begin{problem}[Parallelization, Group action CDH]
  \label{prob:ga-cdh}
  Let $E,E'$ be elliptic curves with complex multiplication by $\O$. %
  Let $\frak a ∈ \Cl(\O)$. %
  Given $(E, \frak a·E, E')$, compute $\frak a·E'$.
\end{problem}

\begin{problem}[Group action DDH]
  \label{prob:ga-ddh}
  Let $E,E'$ be elliptic curves with complex multiplication by $\O$. %
  Let $\frak a ∈ \Cl(\O)$. %
  Given a tuple $(E,\frak a·E,E',E'')$, decide whether
  $E''=\frak a·E'$.
\end{problem}

Each of these problems appears to be legitimately hard, when the
isogeny class is large enough. %
We haven't shown yet that the complex multiplication group action is
an effective one, though. %
We are going to see there is a catch.


\section{Evaluating the CM group action}

At the same time as he introduced the formalism of cryptographic group
actions, Couveignes also indicated the complex multiplication group
action as a candidate. %
His ideas were independently rediscovered by Rostovtsev and
Stolbunov~\cite{EPRINT:RosSto06,Stol}, who were the first to point out
that the schemes thus obtained are plausibly post-quantum. %

However, in order to fulfill the definition of an effective group
action, we need to be able to take an arbitrary element
$\frak a∈\Cl(\O)$, an arbitrary curve $E ∈ \Ell_q(\O)$, and to
evaluate $\frak a · E$. %
But, if we do not choose carefully an ideal representative for
$\frak a$, the norm $N(\frak \a) = \deg ϕ_{\frak a}$ may contain
arbitrarily large prime factors, and we do not necessarily have an
efficient representation for it. %
The best algorithm known for an arbitrary ideal representative has
subexponential complexity in $\log(q)$~\cite{jao+soukharev10}, which
overshoots \hyperref[def:isog-repr]{our definition of
  ``efficient''}. %
Instead, following Rostovtsev and Stolbunov~\cite{EPRINT:RosSto06}, we
may define a variant of the key exchange based on walks in a Cayley
graph of $\Cl(\O)$, which always picks ``efficient'' ideal
representatives.

As an example, let us consider again the action of exponentiation on a
discrete logarithm group. %
Let $H=〈g〉$ be a cyclic group of order $p$, let
$D=\{s_1,\dots,s_n\}⊂(ℤ/pℤ)^{×}$ be a generating set such that $σ∈D$
implies $σ^{-1}∉D$, and let $S = D∪D^{-1}$ so that $S$ is symmetric as
in Definition~\ref{def:cayley}. %
Then, $(ℤ/pℤ)^{×}$ acts on  $H$ minus the identity by
\[e·g_0 = g_0^e\qquad\text{for $e∈(ℤ/pℤ)^×$ and
    $g_0∈H\setminus\{1\}$}.\] %
We may thus define the Schreier graph of
$((ℤ/pℤ)^{×}, S, H\setminus\{1\})$, which is isomorphic to the Cayley
graph $((ℤ/pℤ)^×,S)$; an example for $p=13$ is given in
Figure~\ref{fig:schreier}.


\begin{figure}
  \centering
  \begin{tikzpicture}
    \begin{scope}
      \def\crater{12}
      \def\jumpa{-8}
      \def\jumpb{9}
      \def\diam{2.5cm}

      \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{$g^{\exp}$};
      }
    \end{scope}
    \begin{scope}[xshift=4cm,yshift=1cm]
      \draw[blue] (0,0) -- (0.5,0) (0.5,0) node[black,anchor=west] {$x \mapsto x^{2}$};
      \draw[red] (0,-1) -- (0.5,-1) (0.5,-1) node[black,anchor=west] {$x \mapsto x^{3}$};
      \draw[green] (0,-2) -- (0.5,-2) (0.5,-2) node[black,anchor=west] {$x \mapsto x^{5}$};
    \end{scope}
  \end{tikzpicture}
  \caption{Schreier graph of the generators of a group of order $13$
    under the action of
    $S=\{2,3,5,2^{-1},3^{-1},5^{-1}\}⊂(ℤ/13ℤ)^{×}$.}
  \label{fig:schreier}
\end{figure}

As already seen, a random walk in this graph is a sequence of random
edges starting from some vertex $g_0$ and ending in some vertex
$g_1$. %
However we see that, because the group action of $(ℤ/pℤ)^×$ is
Abelian, the order in which the edges are taken from the set $S$ does
not matter for determining $g_1$: only matters the multiplicity of
each $s∈S$. %
We thus define a \emph{non-backtracking random walk} as a tuple of
multiplicities $(e_1,\dots,e_n)∈ℤ^n$, associated to the element
\[e = \prod_{i=1}^n s_i^{e_i} ∈ (ℤ/pℤ)^×,\]
defining the walk $g_0→e·g_0$. %

We can now define a key exchange protocol where the secrets are
non-backtracking random walks, and the public data are vertices of the
Schreier graph. %
The protocol is summarized in Figure~\ref{fig:walk-dh}.

\begin{figure}
  \centering
  \begin{tabular}{l *{2}{p{30ex}<{\centering}}}
    \hline
    Public parameters & \multicolumn{2}{l}{A group $G$ of prime order $p$,}\\
                      & \multicolumn{2}{l}{A generating set $D⊂(ℤ/pℤ)^{×}$ such that $σ∈D⇒σ^{-1}∉D$,}\\
                      & \multicolumn{2}{l}{A generator $g$ of $G$.}\\
    \hline
                      & {\bf Alice} & {\bf Bob}\\
    \hline
    Pick random secret & $a = \prod_{s∈D}s^{a_i}$ & $b = \prod_{s∈D}s^{b_i}$\\
    Compute public data & $g_a = a·g$ & $g_b = b·g$\\
    Exchange data &  \hfill $g_a \longrightarrow$ & $\longleftarrow g_b$ \hfill\strut \\
    Compute shared secret & $g_{ab} = a·(g_b)$ & $g_{ab} = b·(g_a)$
  \end{tabular}
  
  \caption{Key exchange protocol based on random walks in a Schreier graph.}
  \label{fig:walk-dh}
\end{figure}

Because $g_a = a·g = g^a$, it is evident that this protocol is closely
related to the Diffie--Hellman protocol on the group $G$, the only
difference being that the secret exponents $a,b$ are drawn from an
unusual distribution. %
While this example instance is of no practical interest, its
instantiation using a Schreier graph of the complex multiplication
group action yields a usable variant of Couveignes' key exchange. %
We fix a set $S$ of small norm representatives of ideal classes of
$\Cl(\O)$, corresponding to small degree isogenies between curves in
$\Ell_q(\O)$. %
Instead of uniformly sampling secrets from $\Cl(\O)$, we sample
non-backtracking random walks in the Schreier graph of
$(\Cl(\O),S,\Ell_q(\O))$, and exchange $j$-invariants as public
data. %
The walks can be computed efficiently as a composition of small degree
isogenies, as discussed in Section~\ref{sec:compl-mult-2}. %
Using Theorem~\ref{th:ord-exp}, we know that the graph is an expander
as soon as $\#S \sim (\log q)^2$, thus we can approach the uniform
distribution on $\Ell_q(\O)$ by taking sufficiently long walks. %
Hence we have proved that this mode of sampling secrets can be as good
as sampling uniformly from $\Cl(\O)$, from a security standpoint. %
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}


\section{CSIDH and oriented  supersingular curves}
\label{sec:csidh}

Even with the adjustments of the previous section, the protocol is far
from practical: in 2012 Stolbunov managed to run a 108 bit secure
implementation in around 5 minutes~\cite{Stolbunov2012}. %
To understand why, let's recap how the CM group action is
computed. %
We have a list of primes splitting in $\O$, which are the norms of the
ideals in $S$. %
For one such prime $\ell$, the Frobenius endomorphism splits as
\[π^2 - tπ + q = (π-λ)(π-μ) \mod ℓ,\] %
where we call $λ$ and $μ$ the \emph{eigenvalues of Frobenius} modulo
$ℓ$. %
Thus the ideals in $S$ are $(π-λ,ℓ)$ and $(π-μ,ℓ)$, corresponding to
the two directions on the crater of the $ℓ$-isogeny volcano (see
Section~\ref{sec:compl-mult-2}).

A secret key is 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, the action of $\frak s$ is evaluated by computing
$e_i$ isogenies of degree $N(\a_i)$, for each $\a_i∈S$, thus 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/\F_q$, a prime $ℓ$ and a \emph{direction} $π-λ$. %
Without further assumptions, we need to find a field extension
$\F_{q^n}$ such that $E[ℓ] ⊂ E(\F_{q^n})$, then find the null subspace
of $π-λ$, and finally apply \hyperref[th:velu]{Vélu's formulas}. %
With the extension degree $n$ generally growing as $O(\ell)$, it is no
surprise that evaluating one $\Cl(\O)$-action takes several minutes. %
Better algorithms exist, but they still require $O(ℓ^3)$ operations to
find the isogeny.

Is it possible to do better? %
By choosing parameters carefully, we may hope to limit the degrees of
the extensions where the $E[ℓ]$ live, as first proposed
in~\cite{AC:DeFKieSmi18}. %
Suppose, for example, that $π|E[ℓ]$ acts like $\mat{1&0\\0&q}$, with
$q≠1 \mod ℓ$. %
In this case, there is an easily recognizable direction associated to
the eigenvalue $1$: the corresponding eigenspace is the unique cyclic
group of $\F_q$-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. %
This algorithm is illustrated in Figure~\ref{fig:CM-eval}.

\begin{figure}
  \centering
  \begin{algorithmic}[1]
    \REQUIRE A curve $E$, its order $N = \#E(\F_q)$,\\
    a prime $ℓ$ such that $(π - 1)(π - q) = 0 \mod ℓ$ with $q≠1 \mod ℓ$.
    \ENSURE The curve $(π-1,ℓ)·E$.
    \REPEAT
    \STATE Pick a random point $P$ on $E$;
    \STATE Set $K = [N/ℓ]P$;
    \UNTIL{$K$ is not the point at infinity;}
    \STATE Compute the isogeny $ϕ : E → E/〈K〉$ using Velu's formulas;
    \RETURN $E/〈K〉$.
  \end{algorithmic}
  
  \caption{Evaluation of the CM group action using a special prime.}
  \label{fig:CM-eval}
\end{figure}

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 those points such that $π(x,y) = (x,-y)$, i.e.\
the points whose $x$-coordinate is in $\F_q$ and whose $y$-coordinate
is in $\F_{q^2}$. %
A simple modification to the algorithm in Figure~\ref{fig:CM-eval}
lets us handle both cases at once.%
\footnote{Alternatively, we may note that $E[(π+1,ℓ)]$ is the image of
  $\tilde{E}[(π-1,ℓ)]$, where $\tilde{E}$ is a quadratic twist of
  $E$. %
  Then, acting by $(π-1,ℓ)$ on $\tilde{E}$ and then computing a twist
  has the same effect as acting by $(π+1,ℓ)$ on $E$.} %
This constraint on $π$ forces two conditions:
\begin{enumerate}
\item $N(π) = q=-1 \mod ℓ$,
\item $\Tr(π) = t = 0 \mod\ell$,
\end{enumerate}
and this for each of the norms $ℓ$ 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 second one is much harder, because it essentially requires to find
a curve $E/\F_q$ with a specific trace $t$. %
For $E$ an ordinary curve, the best technique at our disposal
consists, essentially, in taking random curves $E/\F_q$ and computing
$\#E$, until a suitable one is found~\cite{AC:DeFKieSmi18}.

\paragraph{CSIDH.}
On the other hand, if we enforce the constraints above for enough
primes $ℓ$ (it is enough that $\prod ℓ>2\sqrt{q}$), then we
effectively force $t$ to be $0$, and thus $E$ to be supersingular. %
We saw that supersingular curves do not have complex multiplication,
but it turns out there still is a way to define an action of $ℤ[π]$ on
a set of supersingular elliptic curves.

Take a prime field $\F_q$, then any supersingular curve $E/\F_q$ has
trace $0$, i.e.\ its Frobenius satisfies the equation
\[π^2 = -q.\] %
Hence $ℤ[π]$ is a quadratic imaginary order and a subring of
$\End(E)$; it is, in fact, (almost) the subring of $\F_q$-rational
endomorphism of $E$.%
\footnote{There are, in fact, two possibilities for $\End_{\F_p}(E)$,
  namely $ℤ[π]$ or $ℤ[(π-1)/2]$, depending on whether $π-1$ vanishes
  on all of $E[2]$ or not.} %
Then, $\Cl(ℤ[π])$ acts on the set of $\F_q$-isomorphism classes of
supersingular curves, like in the CM case. %
This fact was first observed in~\cite{Delfs2016} and then leveraged
in~\cite{AC:CLMPR18} to define the key exchange protocol
CSIDH\footnote{Pronounced \emph{sea-side}.}, the \emph{Commutative
  Supersingular Isogeny Diffie--Hellman} protocol.

CSIDH uses a prime $q$ of the form $4·\prod_iℓ_i-1$, and the
supersingular curve $y^2 = x^3 - x$ as starting point, so that
$π|E[ℓ_i]=\mat{1&0\\0&-1}$ for all $ℓ_i$. %
By cleverly optimizing computations, CSIDH achieves a key-exchange at
the 128 (classical) bits security level in fractions of a second. %
The scheme is summarized in Figure~\ref{fig:csidh}.

\begin{figure}
  \centering
  \begin{tabular}{l *{2}{p{30ex}<{\centering}}}
    \hline
    Public parameters & \multicolumn{2}{l}{A set of primes $\{ℓ_1,\dots,ℓ_m\}$, a prime $q = 4\prod ℓ_i - 1$,}\\
                      & \multicolumn{2}{l}{A supersingular elliptic curve $E_0$ defined over $\F_q$,}\\
                      & \multicolumn{2}{l}{For each $\ell_i$ the prime ideal $\frak l_i = (ℓ_i,π-1)$,}\\
    \hline
                      & {\bf Alice} & {\bf Bob}\\
    \hline
    Pick random secret & $(a_1,\ldots,a_m) ∈ [-B,B]^m$ & $(b_1,\ldots,b_m) ∈ [-B,B]^m$\\
    Compute public data & $E_A = \left(\prod \frak l_i^{a_i}\right) · E_0$ & $E_B = \left(\prod \frak l_i^{b_i}\right) · E_0$\\
    Exchange data &  \hfill $E_A \longrightarrow$ & $\longleftarrow E_B$ \hfill\strut \\
    Compute shared secret & $E_{AB} = \left(\prod \frak l_i^{e_i}\right) · E_B$ & $E_{AB} = \left(\prod \frak l_i^{b_i}\right) · E_A$
  \end{tabular}
  
  \caption{CSIDH protocol, based on non-backtracking random walks in a
    supersingular CM-like graph.}
  \label{fig:csidh}
\end{figure}

To encompass the ordinary and the supersingular case at once, we
introduce the terminology of orientations. %

\begin{definition}[Oriented curve]
  \label{def:oriented-curve}
  Let $\O$ be an imaginary quadratic order. %
  An \emph{$\O$-oriented curve} is a curve $E$ together with an
  injection $\O \hookrightarrow \End(E)$. %
  If there is no other quadratic order $\O' ⊃ \O$ such that
  $\O' \hookrightarrow \End(E)$, we say that the orientation is
  \emph{primitive}.
\end{definition}

Theorems analogous to the \hyperref[th:compl-mul]{fundamental theorem
  of complex multiplication} apply to oriented curves; in particular,
$\Cl(\O)$ acts faithfully%
\footnote{The action is not always transitive: depending on the case,
  there may be one or two orbits.} %
on primitively $\O$-oriented curves.
See~\cite{ColoKohel+2020+414+437,onuki2021} for details.

Thus, CSIDH is an instance of a $ℤ[π]$-orientation. %
Orientations induced by the Frobenius endomorphism are easy to work
with, because the action of Frobenius on $E[ℓ_i]$ is particularly easy
to compute. %
However, with some extra effort, it is possible to compute the class
group action on many other oriented supersingular isogeny classes:
This was first observed by Kohel and
Coló~\cite{ColoKohel+2020+414+437}, and then leveraged
in~\cite{PKC:DFKLMPW23} to define an analogue of CSIDH, named SCALLOP,
based on orientations by suborders of large prime conductor inside a
maximal order of small discriminant.


\section{Security and quantum computers}

We now do a quick review of the security of protocols based on complex
multiplication. %
The cornerstone of isogeny based cryptography is the \emph{isogeny
  path problem}: given isogenous curves $E$, $E'$, find a path between
them in \emph{some} isogeny graph. %
CM-based protocols are no exception: find an isogeny walk between $E$
and $E'$ in the CM graph, and the \hyperref[prob:gaip]{group action
  inverse problem} is solved. %
We restate this problem using our newly introduced terminology; for
simplicity, we restrict to primitive orientations.

\begin{problem}[Oriented isogeny path problem]
  \label{prob:hiwp}
  \footnote{This problem is almost identical to the \emph{effective
      $\O$-vectorization} problem of~\cite{EC:Wesolowski22}.}  %
  Let $\F_q$ be a finite field, and let $\O$ be a quadratic imaginary
  order $\O ⊂ K$. %
  Given two isogenous primitively $\O$-oriented elliptic curves $E,E'$
  defined over $\F_q$, find an isogeny $E→E'$ of smooth degree.
\end{problem}

Naturally, the first parameter to look at is the size of the
$\O$-oriented isogeny class: too small, and we can find an isogeny by
brute force. %
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)})$, the square root of the
class number of $\O$. %

When $\O$ is the maximal order of $K$, it is known by the class number
formula that $h(\O)$ is in $O(\sqrt{Δ_K}\log Δ_K)$. %
If we take an elliptic curve over $\F_q$ at random, then with
overwhelming probability it will be ordinary and $Δ_K=O(q)$.%
\footnote{The discriminant of Frobenius can be computed in polynomial
  time using Schoof's algorithm (see
  Appendix~\ref{sec:appl-point-count}), then factoring it gives
  $Δ_K$. %
  Thus it is generally feasible to find by trial-and-error ordinary
  curves with an adequately large $Δ_K$.} %
Similarly, in the case of Frobenius-oriented supersingular curves
(i.e., CSIDH and variants) $Δ_K = -4q$ or $Δ_K = -q$. %
Either way, the generic attack runs in $O(q^{1/4})$, which
justifies choosing a prime $q$ of $4n$ bits for a security level of
$2^n$, as done in~\cite{10.1007/978-3-030-03332-3_14,AC:CLMPR18}.

The generic attack is relevant when the distributions of $E$ and $E'$
are independent, e.g.\ when at least one of the two is uniformly
distributed in the class. %
However if the key space of a key exchange scheme is not large enough,
it may be more efficient to perform a brute force search on it. %
Ideally, we would construct CM graphs with a sufficiently large subset
of edges $S⊂\Cl(\O_K)$, and take random walks long enough that
Theorem~\ref{th:ord-exp} applies, thus ensuring that public keys are
uniformly distributed. %
However this is seldom efficient, and practical schemes take instead a
key space just large enough that a search for the secret key is at
least as expensive as the generic algorithm. %

\begin{remark}
  When the orientation is not principal, the first step consists in
  reducing to the principal case using the theory of isogeny
  volcanoes, as first outlined by Galbraith, Hess and
  Smart~\cite{EC:GalHesSma02,galbraith+stolbunov11}.
  
  Let $E$ be $\O$-oriented and let $\O_K ⊃ \O$ be the maximal order. %
  For each prime $ℓ$ dividing the conductor $[\O_K:\O]$ we determine
  the level of $E$ in the $ℓ$-volcano, then an ascending walk to a
  curve on the crater. %
  Repeating for each prime, we obtain an $\O_K$-principally oriented
  curve $\hat{E}$ and a walk $E→\hat{E}$. %
  Doing the same for the second curve $E'$, we reduce to the
  $\O_K$-oriented problem between $\hat{E}$ and $\hat{E}'$.
  
  However, these steps are only doable for ``small'' primes $ℓ$ (say
  $ℓ∈\polylog(q)$). %
  In most practical cases, the conductor $[\O_K:\O]$ will only contain
  a handful of small primes and the reduction applies. %
  One notable exception are the public keys used in
  SCALLOP~\cite{PKC:DFKLMPW23}, which are all principally oriented by
  the same order $\O$ of large prime conductor $f = [\O_K:\O]$. %
  In this case, it can be shown that evaluating the ascending
  $f$-isogeny is in fact equivalent to breaking the system.
\end{remark}


\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. %

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{FOCS:Shor94} 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 group
actions? %

\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{BIJ18,Jao-etal-kuperberg-2018,EC:BonSch20,EC:Peikert20},
Kuperberg's algorithm can be used to solve the \nameref{prob:hiwp} as
follows: let $E,E'$ be the two oriented curves in the same isogeny
class $\mathcal{C}$, define two functions
$f_0,f_1:\Cl(\O)\to\mathcal{C}$ as $f_0(\a)=\a·E$ and $f_1(\a)=\a·E'$,
then the hidden shift corresponds to the class of 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 still
debated~\cite{EC:BLMP19,EC:Peikert20,cryptoeprint:2020:1520}.

\section{Beyond key exchange}
\label{sec:beyond-key-exchange}

The isogeny group action framework can be used to construct many other
interesting cryptographic protocols than key exchange. %
Signature schemes were first sketched by
Couveignes~\cite{EPRINT:Couveignes06} and
Stolbunov~\cite{Stolbunov2012}, and then refined
in~\cite{EC:DeFGal19,AC:BeuKleVer19}.

\textcolor{red}{TODO: this section will be finished at a later
  time. In the meantime, you can find a survey on isogeny based
  signature schemes here~\cite{isogpoksurvey}}

%% TODO: REGA, signatures

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

\clearpage
\part{The full supersingular isogeny graph}
\label{part:ssingular}

All isogeny graphs we have seen so far were governed by the theory of
complex multiplication, and these are essentially the only interesting
graphs of ordinary curves. %
We saw two ways of constructing them: as isogeny graphs of CM curves
in characteristic 0, or as graphs of ordinary curves over finite
fields. %
Deuring's theorems (Theorems~\ref{th:deuring-red}
and~\ref{th:deuring-lift}) showed that these two points of view are
essentially the same, while the correspondence between ideals and
isogenies presented in Section~\ref{sec:compl-mult-2} gave us an
algebraic way to realize the action independently of the base field.

Although we encounter again the same theory in the context of
supersingular curves, for example in the CSIDH group action
(Section~\ref{sec:csidh}), the general theory of these curves is more
complicated. %
As we stated in Theorem~\ref{th:endring}, endomorphism rings of
supersingular curves are 4-dimensional objects, the maximal orders of
a quaternion algebra. %
We have no hope of lifting these to endomorphism rings of curves in
characteristic 0, but \hyperref[th:deuring-lift]{Deuring's lifting
  theorem} gives us a partial result: for every endomorphism
$ω∈\End(E)$, we can find a curve $\bar{E}/ℂ$ and an endomorphism
$\bar{ω}∈\End(\bar{E})$ above it. %
Hence the CM theory of $ℤ[ω]$ still applies to the isogeny class of
$E$, but only describes a small part it.

Said otherwise, while isogeny graphs of ordinary curves are completely
understood as the reduction modulo $p$ of isogeny graphs of CM curves,
supersingular isogeny graphs arise from the simultaneous reduction and
``collision'' of several CM graphs of unrelated quadratic orders. %
This part is devoted to these graphs, and to the theory of
\emph{quaternionic multiplication} that governs them.


\section{Expander graphs from isogenies}

The main object in the study of supersingular isogeny graphs is the
following.

\begin{definition}[Supersingular $\ell$-isogeny graph]
  Fix a prime $\ell ≠ p$, the \emph{(full) supersingular $ℓ$-isogeny
    graph} is the graph of $\bar{\F}_p$-isomorphism classes of
  supersingular curves with $ℓ$-isogenies between them.
\end{definition}

In Section~\ref{sec:ell-isogeny-graphs} we saw how the action of the
Frobenius endomorphism on $E[ℓ]$ controls the number of
$\F_q$-rational isogenies, and thus the structure of the volcano. %
By \hyperref[th:hasse]{Hasse's theorem}, supersingular curves over a
prime field $\F_p$ necessarily have trace $t=0$ and thus Frobenius
acts like a square root of $-p$, giving an embedding
$ℤ[\sqrt{-p}] \hookrightarrow \End(E)$ an the CM action used in CSIDH.

But for supersingular curves over $\F_{p^2}$ the most
common\footnote{The only ones, in fact, except if $j=0,1728$.} cases
are $t = \pm 2p$, and thus Frobenius acts like $\pm p$, fixing any
cyclic subgroup of $E[ℓ]$. %
Said otherwise, all isogenies of a supersingular curve are
$\F_{p^2}$-rational.

\begin{proposition}
  Let $E$ be a supersingular curve defined over a field of
  characteristic $p$. %
  Then
  \begin{itemize}
  \item $j(E) \in \F_{p^2}$;
  \item There exists an isomorphism (not necessarily
    $\F_{p^2}$-rational) from $E$ to a curve $E'/\F_{p^2}$ with trace
    of Frobenius equal to $-2p$;
  \item $E'(\F_{p^2}) ≃ (ℤ/(p+1)ℤ)^2$;
  \item All isogenies and endomorphisms of $E'$ are
    $\F_{p^2}$-rational.
  \end{itemize}
\end{proposition}
\begin{proof}
  See~\cite[Lectures~13--14]{sutherland-notes}
  and~\cite[\S~4]{waterhouse69}.
\end{proof}

By the proposition above, the supersingular $ℓ$-isogeny graph is
isomorphic to the graph of $\F_{p^2}$-isomorphism classes of curves
with trace $-2p$, and every vertex has out-degree $\ell+1$. %
Mapping every isomorphism class to its quadratic twist, we see that it
is also isomorphic to the graph of curves with trace $2p$. %
Two examples of such graphs are shown in
Figure~\ref{fig:sup-97-2-3}. %

Although the graph contains all isogenies with their duals, it is not
necessarily undirected. %
Indeed the vertices $j=0$ and $j=1728$ have larger automorphism groups
(respectively of order 4 and 6, assuming $p > 3$) than any other
curve, and thus have more outgoing than incoming edges. %
Taking $p = 1 \mod 12$ (like in Figure~\ref{fig:sup-97-2-3}) ensures
neither curve is supersingular and sidesteps the problem. %
But even when $p ≠ 1 \mod 12$, we can prove that the adjacency matrix
of the graph has real eigenvalues and apply all the definitions of
Section~\ref{sec:graphs}, obtaining a very powerful result.

\begin{theorem}[Mestre~\cite{mestre86}, Pizer~\cite{pizer1,pizer2}, Kohel~\cite{kohel}]
  \label{th:ss-exp}
  The supersingular $ℓ$-isogeny graph is connected, has real spectrum,
  its largest eigenvalue is $\ell+1$ and every other eigenvalue is
  smaller than $2\sqrt{ℓ}$ in absolute value, i.e.\ it is a Ramanujan
  graph.
\end{theorem}

The standard proof of this result involves Hecke operators acting on
modular forms and is beyond the scope of these lecture notes. %
As explained in~\cite{EPRINT:CFLMP18}, these graphs are distant
cousins of Lubotzky--Phillips--Sarnak (LPS) graphs~\cite{LubPS,Lub},
however, unlike those, do not enjoy the structure of a Cayley graph. %


\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}


\paragraph{The CGL cryptographic hash function.}
The mixing properties of expander graphs have long been used in
computer science to produce pseudo-random behavior. %
In~\cite{JC:ChaLauGor09}, Charles, Goren and Lauter (CGL) used
expander graphs to define cryptographic hash functions. %

Their construction assumes a $k$-regular expander graph is given, with
vertices and edges described by arbitrary unique labels. %
As a first attempt, the graph could be seen as a state machine: for
each vertex $j$, label its outgoing edges from $1$ to $k$ (e.g., by
ordering them alphabetically). %
Then, to hash a $k$-ary string, start from an arbitrary vertex
$j_0$. %
Read the symbols in the string one-by-one, advancing from the current
vertex $j$ to the next vertex $j'$ reached by the edge corresponding
to the read symbol. %
This process defines a pseudo-random walk in the expander graph. %
The hash is the label of the final vertex of the walk.

The only difference between this description and the actual CGL
proposal is that they forbid \emph{backtracking walks}. %
I.e., they use a $(k+1)$-regular graph instead, and only label from
$1$ to $k$ the outgoing edges of the current vertex, excluding the
edge the walk came from (for the first step, an arbitrary forbidden
edge can be chosen). %
This has the advantage of mixing considerably faster than backtracking
walks. %
An example with $k=2$ is pictured in Figure~\ref{fig:hash}.


\begin{figure}
  \centering
  \begin{tikzpicture}
    \coordinate (last) at (0,0);
    \draw (last) node[anchor=east] {$j_0$};
    \foreach \i in {1,...,6} {
      \pgfmathparse{(-1)^\i}
      \let\sign\pgfmathresult
      \pgfmathparse{int(mod(\i+1,2))}
      \let\bit\pgfmathresult
      \pgfmathparse{int(mod(\i,2))}
      \let\nbit\pgfmathresult
      \draw[->] (last) -- (\i,\sign*0.1) node[blue,pos=0.5,yshift=\sign*0.2cm]{\small$\bit$};
      \draw[dashed,->] (last) -- (\i,-\sign*0.5) node[gray,pos=0.5,yshift=-\sign*0.2cm]{\small$\nbit$};
      \coordinate (last) at (\i,\sign*0.1);
    }
    \draw (last) node[anchor=west] {$j_i=H(010101)$};
  \end{tikzpicture}
  \caption{Hashing the string $010101$ using an expander graph}
  \label{fig:hash}
\end{figure}

For the process to be a good pseudo-random function, the walks need to
be substantially longer than the diameter of the graph. %
However this is not enough to guarantee a \emph{cryptographically
  strong} hash function. %
Indeed the two main properties of cryptographic hash functions,
translate in this setting as the following computational problems.

\begin{problem}[Preimage resistance]
  Given a vertex $j$ in the graph, find a path from the start vertex
  $j_0$ to $j$.
\end{problem}

\begin{problem}[Collision resistance]
  Find a non-trivial loop (i.e., one that does not track backwards)
  from $j_0$ to itself.
\end{problem}

Charles, Goren and Lauter suggested two possible instantiations for
the expander graph in the construction above. %
The first was based on LPS Cayley graphs, and was broken shortly after
it was introduced~\cite{EC:TilZem08,SCN:PetLauQui08,SAC:PetQui10}. %

The second was the supersingular $2$-isogeny graph of a large prime. %
Although collision resistance of this proposal has been broken in many
instances~\cite{EC:EHLMP18}, the general problem of computing paths
and cycles in a supersingular isogeny graph remains hard and is the
basis of most of isogeny based cryptography. %
We shall come back to it in Section~\ref{sec:security}.



\section{Quaternionic multiplication aka the Deuring correspondence}
\label{sec:quat-mult-aka}

In Part~\ref{part:isogeny-graphs} we could fully explain the structure
of isogeny volcanoes using the theory of complex multiplication. %
Quaternionic multiplication, also known as the \emph{Deuring
  correspondence}, will help us understand the structure of
supersingular graphs. %

For supersingular elliptic curves $E$, the full endomorphism ring is
isomorphic to a maximal order $\O$ in $B_{p,\infty}$ (the quaternion
algebra over $\Q$ ramified exactly at $p$ and $\infty$). %
We find a correspondence similar to the imaginary quadratic case,
in the sense that (left) ideals of $\O$ correspond to isogenies
with domain $E$, and fractional (left) ideal classes of $\O$
correspond to isomorphism classes of elliptic curves isogenous to $E$.
A major difference is that this no longer provides a group action
on the set of all curves, since the set of fractional ideal classes
no longer admits a group structure.
Also, unlike in the CM case, it is very rare for supersingular
curves to have isomorphic endomorphism rings.

Throughout the text, we have seen several characterizations
of supersingularity, so let us recall:

\begin{theorem}
Let $E$ be a elliptic curve over a field of positive characteristic $p$.
Then the following are equivalent:
\begin{enumerate}
    \item $E$ is supersingular.
    \item $E[p] = \{0\}$.
    \item The map $[p]:E\to E$ is purely inseparable.
    \item The trace $t$ of $\pi_q$, the $q$-Frobenius map,
    is divisible by $p$.
    \item $\End(E)$ is isomorphic to a maximal order in $B_{p,\infty}$.
\end{enumerate}
\end{theorem}

For the rest of the section, we denote by $E$ a supersingular curve
defined over $\F_{p^2}$, and by $\End(E)=\O\subset B_{p,\infty}$ its
endomorphism ring.

Before we dive into the exact relationship between ideals and isogenies
that the Deuring correspondence provides, we need a slightly more
precise relationship between isogenies and subgroups.
Recall from Proposition~\ref{prop:isoker} that separable isogenies
with domain $E$ correspond to finite subgroups of $E$ (namely their kernels).
The same description can be used to treat general isogenies, not only
separable ones, as long as we keep track of the inseparable degree.

\begin{definition}[Separable and inseparable degree]
The \emph{separable degree} of an isogeny $\varphi:E\to E'$ is defined as
$\deg_s(\varphi):= \#\ker(\varphi)$.
The \emph{inseparable degree} $\deg_i(\varphi)$ is defined
by the equation
$\deg(\varphi) = \deg_s(\varphi) \cdot \deg_i(\varphi)$.
\end{definition}

The (in)separable degree of an isogeny equals that of 
the corresponding extension of function fields
(see Definition~\ref{def:degsep}).
In particular, the inseparable degree is always a power of $p$.
The inseparable degree of a separable isogeny is $1$,
and the inseparable degree of a purely inseparable isogeny is equal
to its degree.
The main example of a purely inseparable isogeny is the Frobenius map
$E\to E^{(p)},\:(x,y)\mapsto (x^p,y^p)$, where $E^{(p)}$ denotes the
Weierstrass curve whose coefficients are all raised to the power $p$.
In essence, any other purely inseparable isogeny is a power of the
Frobenius. More precisely, we have the following lemma.

\begin{lemma}\label{lem:insepdecomp}
    Let $\psi:E_1\to E_2$ be an isogeny of elliptic curves such that
    $\deg_i(\psi)=q$. Then there exists a separable isogeny
    $\lambda:E_1^{(q)}\to E_2$ such that $\psi = \lambda\circ\pi_q$,
    where $q:E_1 \to E_1^{(q)}$ denotes the $q$-Frobenius.
\end{lemma}
\begin{proof}
    \cite[II, Coro.~2.12]{silverman:elliptic}
\end{proof}

Where \emph{separable} isogenies correspond to finite subgroups,
arbitrary isogenies correspond to \emph{finite subgroup schemes}.
Essentially, a subgroup scheme is a generalization of a subgroup that
keeps track of information about inseparability.
A precise definition is outside of the scope of these notes, so for
now we will use the following terminology.

\begin{definition}[subgroup scheme]
A \emph{subgroup scheme} is a pair $(H,p^r)$
where $H\subset E$ is a subgroup and $r\in\Z_{\geq 0}$.
The \emph{rank} is defined as $\rk(H,p^r) := \# H \cdot p^r$.
Given two such subgroup schemes, the \emph{scheme-theoretic intersection}
$(H_1,p^r)\cap (H_2,p^s)$ is defined as $(H_1\cap H_2, p^{\min(r,s)})$.
We write $(H_1,p^r)\leq (H_2,p^s)$ if $H_1\subset H_2$ and $r\leq s$.

The \emph{scheme-theoretic kernel} of an isogeny $\varphi: E\to E'$,
denoted $E[\varphi]$, is $(\ker\varphi,\deg_i\varphi)$.
\end{definition}

Conversely, to every finite subgroup scheme $H\leq E$
one can associate an isogeny whose scheme-theoretic kernel is $H$;
similar to Proposition~\ref{prop:isoker}, the codomain $E/H$
of this isogeny is unique up to isomorphism.
The degree of this isogeny equals $\rk H$.

In terms of subgroup schemes, we have the following ``factorization theorem''
for isogenies.

\begin{proposition}
Let $\varphi:E_1\to E_2$ and $\psi:E_1\to E_3$ be isogenies.
If $E[\varphi]\leq E[\psi]$ then there exists an isogeny
$\lambda:E_2\to E_3$ such that $\psi = \lambda\circ\varphi$.
\end{proposition}
%Exercise: proof.

Now we are ready to formulate the Deuring correspondence (compare to
Section~\ref{sec:compl-mult-2}).

\begin{definition}
For an integral left $\O$-ideal $I$, we define
\begin{equation*}
    E[I] := \bigcap_{\alpha\in I} E[\alpha].
\end{equation*}
Conversely, to a subgroup scheme $H\leq E$,
we associate the integral left $\O$-ideal 
\begin{equation*}
    I(H) := \{\alpha\in\O\mid H\leq E[\alpha]\}.
\end{equation*}
\end{definition}

To an integral left $\O$-ideal $I$, we associate the isogeny $\varphi_I$
with kernel $E[I]$ (which is unique up to post-composition by an
isomorphism).

\begin{proposition}
We have $\rk(E[I]) = N(I)$. In other words,
the isogeny $\varphi_I$ has degree $N(I)$.
\end{proposition}

\begin{theorem}[Deuring Correspondence I]\label{thm:deuring1}
    The maps defined above induce a bijection
    \begin{equation*}
        \left\{
            \begin{tabular}{@{} c @{}}
                \emph{subgroup schemes} \\
                $H\leq E$
            \end{tabular}
        \right\}
        \begin{gathered}
            \overset{I(\cdot)}{\xrightarrow{\hspace*{2cm}}} \\[-2ex]
            \underset{E[\cdot]}{\xleftarrow{\hspace*{2cm}}}
        \end{gathered}
        \left\{
            \begin{tabular}{@{} c @{}}
                \emph{integral left} \\
                $\O$\emph{-ideals} $I\subset \O$
            \end{tabular}
        \right\}
    \end{equation*}
\end{theorem}

We say that two fractional left $\O$-ideals $I,J$ are \emph{equivalent}
if there exists a $\beta\in B_{p,\infty}$ such that $I\beta = J$.
In that case we also say that $I,J$ are in the same \emph{left ideal class}.
This happens if and only if $I$ and $J$ are isomorphic as left $\O$-modules.
Every fractional left $\O$-ideal is equivalent to an integral one.

\begin{proposition}\label{prop:idealclasscurve}
    Two integral left $\End(E)$-ideals $I,J$ are equivalent if and only if
    $E/E[I]\cong E/E[J]$.
\end{proposition}

%Exercise: proof (with hints)

This proposition is reminiscent of the \hyperref[th:compl-mul]{main
  theorem of complex multiplication}. %
As a consequence, we have the following ``coarser'' version of
Theorem~\ref{thm:deuring1}, which is what most people refer to as the
Deuring correspondence. %

\begin{theorem}[Deuring correspondence II]
The bijection in Theorem~\ref{thm:deuring1} induces a one-to-one
correspondence
    \begin{equation*}
        \left\{
            \begin{tabular}{@{} c @{}}
                \emph{supersingular elliptic curves over $\F_{p^2}$}\\
                \emph{up to isomorphism}
            \end{tabular}
        \right\}
        \begin{gathered}
            \overset{}{\xrightarrow{\hspace*{2cm}}} \\[-2ex]
            \underset{}{\xleftarrow{\hspace*{2cm}}}
        \end{gathered}
        \left\{
            \begin{tabular}{@{} c @{}}
                \emph{fractional left} \\
                $\O$\emph{-ideal classes}
            \end{tabular}
        \right\}
    \end{equation*}
\end{theorem}

In summary, the same correspondences between ideals and isogenies
given in Table~\ref{tab:cm} for complex multiplication also hold for
the Deuring correspondence. %
Unlike in the CM case, left $\O$-ideal classes do not form a group,
though at least we obtain the exact size of the left ideal class set,
and thus of the supersingular isogeny class, thanks to Eichler's mass
formula. %

\begin{corollary}\label{cor:eichlermass}
  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}

There also exists a more precise, functorial statement of the Deuring
correspondence, which we give here for completeness. %
The reader unfamiliar with categories can safely ignore this version.

\begin{lemma}
    Given an isogeny $\varphi:E_1\to E_2$, the pullback map
    $\Hom(E_2,E_1)\to\End(E_1), \psi\mapsto \psi\circ\varphi$
    is an injective morphism of left $\End(E_1)$-modules.
    In particular, it is an isomorphism onto the image $I(E_1[\varphi])$.
\end{lemma}

\begin{theorem}[Deuring correspondence III]
  \label{th:deuring-funct}
    The contravariant functor $\Hom(-,E)$
    defines an equivalence of categories
    \begin{equation*}
        \left\{
            \begin{tabular}{@{} c @{}}
                \emph{supersingular elliptic curves over $\F_{p^2}$}, \\
                \emph{with isogenies}
            \end{tabular}
        \right\}
        \begin{gathered}
            \overset{}{\xrightarrow{\hspace*{2cm}}} \\[-2ex]
            \underset{}{\xleftarrow{\hspace*{2cm}}}
        \end{gathered}
        \left\{
            \begin{tabular}{@{} c @{}}
                \emph{invertible left $\End(E)$-modules}, \\
                \emph{with nonzero homomorphisms}
            \end{tabular}
        \right\}
    \end{equation*}
\end{theorem}

\paragraph{Endomorphism rings.}
Using the Deuring correspondence, we were able to count the number of
isomorphism classes of supersingular elliptic curves.  %
Each such supersingular elliptic curve has an endomorphism ring
isomorphic to some maximal order in $B_{p,\infty}$. %
We saw that quadratic number fields have a unique maximal order, so it
is natural to ask whether something similar happens in quaternion
algebras. %
In other words, what is the number of isomorphism classes of
\emph{endomorphism rings} of supersingular elliptic curves?

We say two maximal orders $\O,\O'\subset B_{p,\infty}$
are \emph{conjugate} if there exists a $\beta\in B_{p,\infty}$ such
that $\O' = \beta\O\beta^{-1}$. This is equivalent to $\O$ and $\O'$
being isomorphic as rings.
If $I$ is an integral left $\O$-ideal, then by the Deuring
correspondence we obtain an isogeny $\varphi_I : E\to E'$
with kernel $E[I]$.
One can then show that $\O_L(I)=\O\cong\End(E)$
and $\O_R(I)=\O'\cong\End(E')$.
Such an ideal $I$ is called a \emph{connecting ideal}
for the orders $\O$ and $\O'$. 
Note that, since $\O_R(I\beta)=\beta^{-1}\O'\beta$ for every
$\beta\in B_{p,\infty}$, ideals equivalent to $I$ indeed
have conjugate (hence isomorphic) right orders. %

Now suppose that $\O$ and $\O'$ are isomorphic. By taking a different
representative for the same fractional ideal class,
we then may assume that $I$ is such that $\O=\O'$.
In other words, $I$ is a \emph{two-sided}
$\O$-ideal. Just like in the imaginary quadratic case, the
two-sided fractional ideals form a group, and by considering them up to
equivalence, we obtain the \emph{(two-sided) ideal class group}
$\Pic(\O)$ of $\O$.
We have the following result about its structure.
\begin{theorem}
There is a unique two-sided fractional $\O$-ideal of norm $p$.
It generates the two-sided ideal class group $\Pic(\O)$ of $\O$.
As an element of this group it has order at most $2$.
\end{theorem}
Under the Deuring correspondence, this special two-sided fractional
$\O$-ideal of norm $p$
corresponds to the Frobenius $E\to E^{(p)}$.
In particular, the group $\Pic(\O)$ is trivial if and only if $E$ is
defined over $\F_p$, and it is isomorphic to $\Z/2\Z$ if and only if
$E$ is not defined over $\F_p$ (recall that $E$, being supersingular,
is automatically defined over $\F_{p^2}$).
We can summarize as follows:
\begin{theorem}
There is a one-to-one correspondence:
    \begin{equation*}
        \left\{
            \begin{tabular}{@{} c @{}}
                \emph{supersingular $j$-invariants}, \\
                \emph{up to the action of Frobenius}
            \end{tabular}
        \right\}
        \begin{gathered}
            \overset{}{\xrightarrow{\hspace*{2cm}}} \\[-2ex]
            \underset{}{\xleftarrow{\hspace*{2cm}}}
        \end{gathered}
        \left\{
            \begin{tabular}{@{} c @{}}
                \emph{maximal orders $\O\subset B_{p,\infty}$}, \\
                \emph{up to conjugacy}
            \end{tabular}
        \right\}
    \end{equation*}
\end{theorem}


\section{The effective Deuring correspondence}
\label{sec:eff-deuring}

The correspondence between ideal classes of quadratic orders and
isogenies let us efficiently evaluate the CM action and construct
isogeny-based cryptographic schemes, as described in
Part~\ref{part:crypt-group-acti}. %
We would like to have an analogous collection of algorithms for the
Deuring correspondence.

The first step is to establish an \emph{efficient representation} of
an endomorphism ring. %
Concretely, for a given curve $E_0$, we seek a basis of $\End(E_0)$
made of four \hyperref[def:isog-repr]{efficiently represented}
endomorphisms, together with an explicit injection
$\End(E_0) \hookrightarrow B_{p,∞}$.

This is easier said than done: ordinary curves have an obvious
endomorphism generating the endomorphism algebra, the Frobenius
endomorphism, and finding a corresponding algebraic integer amounts to
computing its minimal polynomial, or equivalently to counting the
number of points of the curve (see
Appendix~\ref{sec:appl-point-count}). %
For supersingular curves, on the other hand, it is in general
difficult to find even a single endomorphism. %
Luckily, some curves have a natural quaternion representation.

\begin{proposition}
  \label{th:E0}
  Let $B_{p,∞}$ be represented as in
  Proposition~\ref{th:quat-presentation} and let $\O_0$ be the maximal
  order of Proposition~\ref{th:quat-max-ord}. %
  Assuming the generalized Riemann hypothesis (GRH), there exists a
  supersingular curve $E_0$ such that $\End(E_0)≃\O_0$ and a basis of
  $\End(E_0)$ made of efficiently represented endomorphisms.
\end{proposition}
\begin{proof}
  If $p = 2$, then $E_0$ is the curve $y^2 + y = x^3$ with
  $j$-invariant 0, $(1 + i + j + ij)/2$ is one of its automorphisms of order
  $6$, $i$, $j$ and $k$ are automorphisms of order $4$.
  
  For all other cases, we follow~\cite[Proposition~3]{EC:EHLMP18}. %
  If $p ≡ 3 \bmod 4$, then $E_0$ is again $y^2 = x^3 + x$, with the
  automorphism $ι:(x,y)↦(-x,\sqrt{-1} y)$ for $i$ and Frobenius for
  $j$ (see Example~\ref{ex:1728}).

  For $p ≡ 5 \bmod 8$, we choose $E_0 : y^2 = x^3 + x^2 - 3x + 1$ of
  $j$-invariant $8000$. %
  This curve has a single point of order $2$ defined over $ℚ$,
  generating the kernel of an endomorphism of degree $2$, take its
  reduction for $i$. %
  The Frobenius endomorphism corresponds to $j$.
  
  Finally, for $p ≡ 1 \bmod 8$, consider the maximal order $\O$ of
  $ℚ(\sqrt{-r})$: because $q = 3 \mod 4$, its class number must be odd
  (see~\cite{mordell61}). %
  By hypothesis
  $\left(\frac{r}{p}\right) = \left(\frac{-r}{p}\right) = -1$, thus by
  Theorem~\ref{th:deuring-red} all curves over $ℂ$ with CM by $\O$
  have supersingular reduction modulo $p$. %
  Because they are odd in number at least one of these reductions must
  be defined over $\F_p$, let it be $E_0$. %
  Finally, let $ι$ be one of its endomorphisms such that $ι^2 = -r$,
  then the quaternion $i$ corresponds to $ι$ and $j$ corresponds to
  the $\F_p$-Frobenius endomorphism.

  Assuming GRH, the smallest $r$ satisfying the conditions of
  Proposition~\ref{th:quat-presentation} is in $O(\log(p)^2)$. %
  Then all the computations above can be done in time $\polylog(p)$,
  which fits within the budget of Defintion~\ref{def:isog-repr}.
\end{proof}

From now on we shall call \emph{special} a supersingular curve
produced by the proposition. %
In practice, virtually all supersingular isogeny based cryptography
uses $p = 3 \mod 4$ and sets $E_0:y^2 = x^3 + x$. %
We shall thus only focus on this case in the rest of the manuscript.

Having an efficient representation of $\End(E_0)$ is sufficient, in
principle, to efficiently represent the endomorphism ring of any other
curve in the isogeny class. %
Indeed, from the Deuring correspondence we have the following
description of $\End(E)$ for any curve isogenous to $E_0$.

\begin{proposition}
  Let $ϕ : E_0 → E$ be an isogeny of supersingular curves and let
  $ι_0 : \End(E_0) \hookrightarrow \O_0 ⊂ B_{p,∞}$ be a representation of $\End(E_0)$. %
  The map
  \begin{align*}
    ι_ϕ : \End(E) &\hookrightarrow B_{p,∞}\\
    ω &\mapsto \frac{ι_0(\hat{ϕ}∘ω∘ϕ)}{\deg ϕ}
  \end{align*}
  is injective and $ι_ϕ(\End(E)) = \O_R(I(E_0[ϕ]))$.
\end{proposition}
\begin{proof}
  See~\cite[Lemma~42.2.10]{Voight2018}.
\end{proof}

Said otherwise, we have an explicit representation of $\End(E)$ as a
subring of $B_{p,∞}$ as soon as we have an isogeny $ϕ:E_0→E$, but is
it an efficient representation? %
Suppose we have a quaternion $α ∈ B_{p,∞}$ representing an
endomorphism of $E$, and let $d = \deg ϕ$. %
Applying the isomorphism backwards we know there exists
$ω_0 ∈ \End(E_0)$ such that $ι_0(ω_0) = dβ$; then, 
\[ι_0^{-1}(dβ) = ω_0 = \hat{ϕ} ∘ ω ∘ ϕ\]
and
\[d^2 ω = ϕ ∘ ω_0 ∘ \hat{ϕ},\] %
and every $ω ∈ \End(E)$ can be written this way. %
Suppose we want to evaluate $ω$ at a point $P ∈ E$, we can compute $Q$
such that $[d^2]Q = P$, then
\[ϕω_0\hat{ϕ}(Q) = d^2ω(Q) = ω(P).\]
Thus we have an efficient representation of $ω$ as long as:
\begin{enumerate}
\item $ϕ$ is efficiently represented,
\item we can efficiently ``divide by $d^2$''.
\end{enumerate}

Let us start from the case where $d$ is ``small'', then
\hyperref[th:velu]{Vélu's formulas} provide an efficient
representation of $ϕ$. %
Moreover, if $P ∈ E(\F_q)$, a point $Q$ such that $[d^2]Q = P$ is
defined in an extension of $\F_q$ of degree less than $d^4$ (see
Appendix~\ref{sec:appl-point-count} and in particular
Definition~\ref{def:divpol}). %
Hence, we have an efficient representation of $ω$ whenever
$d ∈ \polylog(p)$.

We easily extend this to the case where $d$ is \emph{powersmooth},
i.e.\ where $d = \prod_{i=1}^n ℓ_i^{e_i}$ with the $ℓ_i$ coprime and
$n,ℓ_i^{e_i} ∈ \polylog(p)$. %
Indeed, by Corollary~\ref{coro:isog-basic}, $ϕ$ can be efficiently
represented as a composition of isogenies of degree $ℓ_i$. %
Dividing by $d^2$ is trickier: for each $i$ we can efficiently compute
$Q_i$ such that $[ℓ_i^{2e_i}]Q_i = P$, implying that $Q = \sum_i Q_i$
satisfies $[d^2]Q = P$. %
Then we evaluate $ϕω_0\hat{ϕ}(Q)$ as
\[ϕω_0\hat{ϕ}(Q) = ϕω_0\hat{ϕ}\left(\sum_i Q_i\right) = \sum_i
  ϕω_0\hat{ϕ}(Q_i),\] %
involving only computations in extensions of $\F_q$ of degree less
than $ℓ_i^{4e_i}$ and a final chain of point additions over $\F_q$.

In summary, whenever we know an isogeny $ϕ:E_0→E$ of powersmooth
degree, we have an efficient representation of $\End(E)$. %
Knowledge of endomorphism rings is contagious! %
We can prove that such an isogeny always exists.

\begin{proposition}
  Let $E_0$ be a special curve as defined by Proposition~\ref{th:E0},
  let $E$ be an arbitrary curve in the same isogeny class, then,
  assuming GRH, there exists an isogeny $ϕ:E_0→E$ of degree
  $\polylog(p)$-powersmooth.
\end{proposition}
\begin{proof}
  Thanks to the Deuring correspondence, after fixing an appropriate
  smoothness bound $B ∈ \polylog(p)$, it suffices to prove that any
  ideal class of $\O_0$ contains an ideal of $B$-powersmooth norm. %
  See~\cite{FOCS:Wesolowski21} for details.
\end{proof}

Even though $ϕ:E_0→E$ always exists, it is not necessarily easy to
find. %
We will come back to the problem of computing isogenies of
supersingular curves and its relationship to computing their
endomorphsim rings in Section~\ref{sec:security}.


\section{Signatures based on the Deuring correspondence}
\label{sec:sqisign}

\textcolor{red}{TODO: this section will cover the signature schemes
  GPS~\cite{JC:GalPetSil20} and SQISign~\cite{AC:DKLPW20} (see also
  \url{https://sqisign.org/}).}


\section{Security of supersingular isogeny problems}
\label{sec:security}

\textcolor{red}{TODO: this section will cover the security reductions
  between hard problems in supersingular isogeny
  cryptography~\cite{EC:Wesolowski22} and in particular the
  equivalence between the isogeny path problem and the endormorphism
  ring problem~\cite{FOCS:Wesolowski21}.}

% TODO: EndRing, IsoPath, SIDH, $Γ$-SIDH, reductions, attacks

% \begin{problem}[Isogeny computation]
%   Let $E$ be an elliptic curve defined over some field $k$. %
%   Given a description (e.g.\ a list of generators) of a subgroup
%   $G⊂E(k)$ of order $ℓ$, compute the rational fractions and the image
%   curve of the unique separable isogeny of kernel $G$.
% \end{problem}

% A slight variation on this problem asks to output, instead of the full
% rational fractions representing the isogeny, simply its evaluation at
% a point.

% \begin{problem}[Isogeny evaluation]
%   Let $E$ be an elliptic curve defined over some field $k$. %
%   Given a description of a subgroup $G⊂E(k)$ of order $ℓ$, given a
%   point $P∈E$, letting $ϕ$ be the unique separable isogeny of kernel
%   $G$, compute $ϕ(P)$.
% \end{problem}

% The following problems are less central to isogeny based
% cryptosystems, but appear, e.g., when counting points of elliptic
% curves.

% \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}
%   Given two elliptic curves $E,E'$, isogenous of known degree $ℓ$,
%   find an isogeny $ϕ:E\to E'$ of degree $ℓ$.
% \end{problem}

% Elkies was the first to formulate these two problems and give an
% algorithm~\cite{elkies92,elkies98} that solves both with complexity
% $O(\ell^3)$ in
% general~\cite{bostan+morain+salvy+schost08,lercier+sirvent08}. %
% Alternate algorithms, with similar complexity, are due to Couveignes
% and
% others~\cite{couveignes94,couveignes96,couveignes00,df+schost09,defeo2016explicit}.

% All previous problems can be considered to be "easy" problems,
% because they have a polynomial time solution in the size of their
% output. %
% The next problem is the blueprint for all "hard" isogeny problems used in
% isogeny based cryptography. %

% \begin{problem}[Isogeny path]
%   Given two elliptic curves $E,E'$ over a finite field $\F_q$, such that
%   $\#E=\#E'$, find an isogeny $ϕ:E\to E'$ of smooth degree.
% \end{problem}

% The difficulty of this problem depends on the distributions $E$ and
% $E'$ are drawn from, but it is in general a very difficult one, for
% which only algorithms exponential in $\log(q)$ are known. %
% Remark that, in general, $\degϕ$ will be exponential in $\log(q)$,
% hence the "smooth degree" constraint, which lets us represent the
% output as a composition of small degree isogenies.

% A general strategy to tackle the problem is by a \emph{meet in the
%   middle} random walk~\cite{Gal}: choose an expander graph $G$
% containing both $E$ and $E'$, and start a random walk from each
% curve. %
% By the birthday paradox, the two walks are expected to meet after
% roughly $O(\sqrt{\#G})$ steps; when a collision is detected, the
% composition of the walks yields the desired isogeny.

% The meet in the middle strategy was notoriously used to extend the
% power of the GHS attack on elliptic curves defined over extension
% fields of composite degree~\cite{JC:GauHesSma02,EC:GalHesSma02}. %
% Without going into the details of the GHS attacks, one of its
% remarkable properties is that only a small fraction of a given isogeny
% class is vulnerable to it. %
% Finding an isogeny from an immune curve to a weak curve allows the
% attacker to map the discrete logarithm problem from one to the
% other. %
% The average size of the isogeny class of a random ordinary elliptic
% curve is $O(\sqrt{\#E})$ (more on this later), thus the meet in the
% middle strategy yields an $O(\#E^{1/4})$ attack on any curve in the
% class: better than a generic attack on the discrete logarithm
% problem. %
% The attack is pictured in Figure~\ref{fig:ghs}.

% \begin{figure}
%   \centering
%   \begin{tikzpicture}
%     \path (0,0) node[anchor=east] {$E$} (6,0) node[anchor=west] {$E'$};
%     \path (-0.8,0) node[anchor=east] {weak curve}
%     (6.8,0) node[anchor=west] {strong curve};

%     \draw[->] (0,0) -- (0.5,-0.2);
%     \draw[->] (6,0) -- (5.5,0.2);
%     \draw[->] (0.5,-0.2) -- (1,0.2);
%     \draw[->] (5.5,0.2) -- (5,-0.2);
%     \begin{scope}[densely dotted,coils/.style={decorate,decoration={coil,aspect=0,amplitude=2pt}}]
%       \draw[coils] (1,0.2) -- (3,0.4);
%       \draw[coils] (5,-0.2) -- (3,0.4);
%       \draw[-angle 90,coils] (3,0.4) -- (3, -0.4) node[anchor=north] {$E''$};
%     \end{scope}
%   \end{tikzpicture}
%   \caption{The meet in the middle attack in weak isogeny classes.}
%   \label{fig:ghs}
% \end{figure}

% Similar ideas have been used to construct \emph{key escrow
%   systems}~\cite{JC:Teske06}, and to prove random reducibility of
% discrete logarithms inside some isogeny
% classes~\cite{jao+miller+venkatesan09}.


% \section{SIDH-like proofs of knowledge}
% \label{sec:sidh-poks}

% TODO


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
\addcontentsline{toc}{part}{References}
\bibliographystyle{plainurl}
\bibliography{refs,isogenies_bib/isogenies,cryptobib/abbrev3,cryptobib/crypto}

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

\clearpage
\appendix
\part{Other applications}

This material used to be part of the first version of these lecture
notes, but we decided to discard it from the main body to focus on the
more central topics.

We keep it in this appendix for historical reference, however we do
not guarantee its coherence with the main material.

\section{Application: Elliptic curve factoring method}

A second popular use of elliptic curves in technology is for factoring
large integers, a problem that also occurs frequently in cryptography.

The earliest method for factoring integers was already known to the
ancient Greeks: the \emph{sieve of Eratosthenes} finds all primes up
to a given bound by crossing composite numbers out in a table. %
Applying the Eratosthenes' sieve up to $\sqrt{N}$ finds all prime
factors of a composite number $N$. %
Examples of modern algorithms used for factoring are Pollard's
\emph{Rho algorithm} and Coppersmith's \emph{Number Field Sieve
  (NFS)}.

In the 1980s H. Lenstra~\cite{lenstra87} introduced an algorithm for
factoring that has become known as the \emph{Elliptic Curve Method
  (ECM)}. %
Its complexity is between Pollard's and Coppersmith's algorithms in
terms of number of operations; at the same time it only requires a
constant amount of memory, and is very easy to parallelize. %
For these reasons, ECM is typically used to factor integers having
medium sized prime factors.

From now on we suppose that $N=pq$ is an integer which factorization
we wish to compute, where $p$ and $q$ are distinct primes. %
Without loss of generality, we can suppose that $p<q$.

Lenstra's idea has its roots in an earlier method for factoring
special integers, also due to Pollard. %
Pollard's \emph{$(p-1)$ factoring method} is especially suited for
integers $N=pq$ such that $p-1$ only has \emph{small} prime factors. %
It is based on the isomorphism
\begin{align*}
  \rho : ℤ/Nℤ &\to ℤ/pℤ × ℤ/qℤ,\\
  x &\mapsto (x \bmod p, x \bmod q)
\end{align*}
given by the Chinese remainder theorem. %
The algorithm is detailed in Figure~\ref{fig:p-1}. %
It works by guessing a multiple $e$ of $p-1$, then taking a random
element $x∈(ℤ/Nℤ)^{×}$, to deduce a random element $y$ in
$〈1〉⊕(ℤ/qℤ)^{×}$. If the guessed exponent $e$ was correct, and if
$y≠1$, the gcd of $y-1$ with $N$ yields a non-trivial factor. %

\begin{figure}
  \begin{subfigure}{0.45\textwidth}
    \begin{algorithmic}[1]
      \REQUIRE An integer $N=pq$,\\
      a bound $B$ on the largest prime factor of $p-1$;
      \ENSURE $(p,q)$ or FAIL.
      \STATE Set $e = \prod_{r \text{ prime } < B} r^{\lfloor\log_r\sqrt{N}\rfloor}$;
      \STATE Pick a random $1 < x < N$;
      \STATE Compute $y = x^e \mod N$;
      \STATE Compute $q' = \gcd(y-1, N)$;
      \IF {$q' ≠ 1,N$}
      \RETURN $N/q', q'$;
      \ELSE
      \RETURN FAIL.
      \ENDIF
    \end{algorithmic}
    
    \caption{Pollard's $(p-1)$ algorithm}
    \label{fig:p-1}
  \end{subfigure}
  %% 
  \hfill
  %% 
  \begin{subfigure}{0.45\textwidth}
    \begin{algorithmic}[1]
      \REQUIRE An integer $N=pq$, a bound $B$;
      \ENSURE $(p,q)$ or FAIL.
      \STATE Pick random integers $a,X,Y$ in $[0,N[$;
      \STATE Compute $b = Y^2 - X^3 - aX \mod N$;
      \STATE Define the elliptic curve $E \;:\; y^2 = x^3 - ax - b$.
      \STATE Define the point $P=(X:Y:1) ∈ E(ℤ/Nℤ)$.
      \STATE Set $e = \prod_{r \text{ prime } < B} r^{\lfloor\log_r\sqrt{N}\rfloor}$;
      \STATE Compute $Q = [e]P = (X':Y':Z')$;
      \STATE Compute $q' = \gcd(Z', N)$;
      \IF {$q' ≠ 1,N$}
      \RETURN $N/q', q'$;
      \ELSE
      \RETURN FAIL.
      \ENDIF
    \end{algorithmic}
    
    \caption{Lenstra's ECM algorithm}
    \label{fig:ecm}
  \end{subfigure}
  \caption{The $(p-1)$ and ECM factorization algorithms}
\end{figure}

The $p-1$ method is very effective when the bound $B$ is small, but
its complexity grows exponentially with $B$. %
For this reason it is only usable when $p-1$ has small prime factors,
a constraint that is very unlikely to be satisfied by random primes.

Lenstra's ECM algorithm is a straightforward generalization of the
$p-1$ method, where the multiplicative groups $(ℤ/pℤ)^{×}$ and
$(ℤ/qℤ)^{×}$ are replaced by the groups of points $E(\F_p)$ and
$E(\F_q)$ of an elliptic curve defined over $ℚ$. %
Now, the requirement is that $\#E(\F_p)$ only has small prime
factors. %
This condition is also extremely rare, but now we have the freedom to
try the method many times by changing the elliptic curve. %

The algorithm is summarized in Figure~\ref{fig:ecm}. %
It features two remarkable subtleties. %
First, it would feel natural to pick a random elliptic curve
$E:y^2=x^3+ax+b$ by picking random $a$ and $b$, however taking a point
on such curve would then require computing a square root modulo $N$, a
problem that is known to be has hard as factoring $N$. %
For this reason, the algorithm starts by taking a random point, and
then deduces the equation of $E$ from it. %
Secondly, all computations on coordinates happen in the projective
plane over $ℤ/Nℤ$; however, properly speaking, projective space cannot
be defined over non-integral rings. %
Implicitly, $E(ℤ/Nℤ)$ is defined as the product group
$E(\F_p)⊕E(F_q)$, and any attempt at inverting a non-invertible in
$ℤ/Nℤ$ will result in a factorization of $N$.


\section{Application: point counting}
\label{sec:appl-point-count}

Before going more in depth into the study of the endomorphism ring,
let us pause for a while on a simpler problem. %
Hasse's theorem relates the cardinality of a curve defined over a
finite field with the trace of its Frobenius endomorphism. %
However, it does not give us an algorithm to compute either.

The first efficient algorithm to compute the trace of $π$ was proposed
by Schoof in the 1980s~\cite{schoof85}. %
The idea is very simple: compute the value of $t_π\bmod ℓ$ for many
small primes $ℓ$, and then reconstruct the trace using the Chinese
remainder theorem. %
To compute $t_π\bmod ℓ$, Schoof's algorithm formally constructs the
group $E[ℓ]$, takes a generic point $P∈E[\ell]$, and then runs a
search for the integer $t$ such that
\[π([t]P) = [q]P + π^2(P).\] %
The formal computation must be carried out by computing modulo a
polynomial that vanishes on the whole $E[\ell]$; the smallest such
polynomial is provided by the \emph{division polynomial} $ψ_ℓ$.

\begin{definition}[Division polynomial]
  \label{def:divpol}
  Let $E:y^2=x^3+ax+b$ be an elliptic curve, the \emph{division
    polynomials} $ψ_m$ are defined by the initial values
  \begin{align*}
    ψ_1 &= 1,\\
    ψ_2 &= 2y,\\
    ψ_3 &= 3x^4 + 6ax^2 + 12bx - a^2,\\
    ψ_4 &= (2x^6 + 10ax^4 + 40bx^3 - 10a^2x^2 - 8abx - 2a^3 - 16b^2)2y,
  \end{align*}
  and by the recurrence
  \begin{align*}
    ψ_{2m+1}  &= ψ_{m+2}ψ_m^3 - ψ_{m-1}ψ_{m+1}^3 &\text{for $m≥2$,}\\
    ψ_2ψ_{2m} &= (ψ_{m+2}ψ_{m-1}^2 - ψ_{m-2}ψ_{m+1}^2)ψ_m &\text{for $m≥3$.}
  \end{align*}

  The $m$-th division polynomial $ψ_m$ vanishes on $E[m]$;
  the multiplication-by-$m$ map can be written as
  \[[m]P = \left(\frac{ϕ_m(P)}{ψ_m(P)^2}, \frac{ω_m(P)}{ψ_m(P)^3}\right)\]
  for any point $P≠\O$, where $ϕ_m$ and $ω_m$ are defined as
  \begin{align*}
    ϕ_m &= xψ_m^2 - ψ_{m+1}ψ_{m-1},\\
    ω_m &= ψ_{m-1}^2ψ_{m+2} + ψ_{m-2}ψ_{m+1}^2.
  \end{align*}
\end{definition}

Schoof's algorithm runs in time polynomial in $\log\#E(k)$, however it
is quite slow in practice. %
Among the major advances that have enabled the use of elliptic curves
in cryptography are the optimizations of Schoof's algorithm due to
Atkin and Elkies~\cite{atkin91,elkies92,schoof95,elkies98}. %
Both improvements use a better understanding of the action of $π$ on
$E[ℓ]$. %
Assume that $ℓ$ is different from the characteristic, we have already
seen that $E[ℓ]$ is a group of rank two. %
Hence, $π$ acts on $E[ℓ]$ like a matrix $M$ in $\GL_2(ℤ/ℓℤ)$, and its
characteristic polynomial is exactly
\[χ(X) = X^2 - t_πX + q \mod \ell.\] %
Now we have three possibilities:
\begin{itemize}
\item $χ$ splits modulo $ℓ$, as $χ(X) = (X-λ)(X-μ)$, with $λ≠μ$; we call
  this the \emph{Elkies case}.
\item $χ$ does not split modulo ℓ; we call this the \emph{Atkin case};
\item $χ$ is a square modulo $ℓ$.
\end{itemize}

The SEA algorithm, treats each of these cases in a slightly different
way; for simplicity, we will only sketch the Elkies case. %
In this case, there exists a basis $〈P,Q〉$ for $E[ℓ]$ onto which $π$
acts as a matrix
$M=\left(\begin{smallmatrix}λ&0\\0&μ\end{smallmatrix}\right)$. %
Each of the two eigenspaces of $M$ is the kernel of an isogeny of
degree $ℓ$ from $E$ to another curve $E'$. %
If we can determine the curve corresponding to, e.g., $〈P〉$, then we
can compute the isogeny $ϕ:E\to E/〈P〉$, and use it to formally
represent the point $P$. %
Then, $λ$ is recovered by solving the equation
\[[λ]P = π(P),\]
and from it we recover $t_π = λ + q/λ \mod \ell$.

Elkies' method is very similar to Schoof's original way of computing
$t_π$, however it is considerably more efficient thanks to the degree
of the extension rings involved. %
Indeed, in Schoof's algorithm a generic point of $E[ℓ]$ is represented
modulo the division polynomial $ψ_ℓ$, which has degree $(ℓ^2-1)/2$. %
In Elkies' algorithm, instead, the formal representation of $〈P〉$
only requires working modulo a polynomial of degree $≈ℓ$.

The other cases have similar complexity gains. %
For a more detailed overview, we address the reader
to~\cite{schoof95,lercier-algorithmique,elkies98,sutherland10}.


\section{Application: computing irreducible polynomials }

In the applications seen in the first part, we have followed an old
\emph{mantra}: whenever an algorithm relies solely on the properties
of the multiplicative group $\F_q^*$, it can be generalized by
replacing $\F_q^*$ with the group of points of an elliptic curve over
$\F_q$ (or, eventually, a higher dimensional Abelian variety). %
Typically, the generalization adds some complexity to the computation,
but comes with the advantage of having more freedom in the choice of
the group size and structure. %
We now present another instance of the same \emph{mantra}, that is
particularly remarkable in our opinion: to the best of our knowledge,
it is the first algorithm where replacing $\F_q^*$ with $E(\F_q)$
required some non-trivial work with isogenies.

Constructing irreducible polynomials of arbitrary degree over a finite
field $\F_q$ is a classical problem. %
A classical solution consists in picking polynomials at random, and
applying an irreducibility test, until an irreducible one is found. %
This solution is not satisfactory for at least two reasons: it is not
deterministic, and has average complexity quadratic both in the degree
of the polynomial and in $\log q$.

For a few special cases, we have well known irreducible polynomials. %
For example, when $d$ divides $q-1$, there exist $α∈\F_q$ such that
$X^d-α$ is irreducible. %
Such an $α$ can be computed using Hilbert's theorem 90, or --more
pragmatically, and assuming that the factorization of $q-1$ is known--
by taking a random element and testing that it has no $d$-th root in
$\F_q$. %
It is evident that this algorithm relies on the fact that the
multiplicative group $\F_q^*$ is cyclic of order $q-1$.

At this point our \emph{mantra} suggests that we replace $α$ with a
point $P∈E(\F_q)$ that has no $ℓ$-divisor in $E(\F_q)$, for some well
chosen curve $E$. %
The obvious advantage is that we now require $ℓ|\#E(\F_q)$, thus we
are no longer limited to $ℓ|(q-1)$; however, what irreducible
polynomial shall we take? %
Intuition would suggest that we take the polynomial defining the
$ℓ$-divisors of $P$; however we know that the map $[ℓ]$ has degree
$ℓ^2$, thus the resulting polynomial would have degree too large, and
it would not even be irreducible.

This idea was first developed by Couveignes and
Lercier~\cite{couveignes+lercier11} and then slightly generalized
in~\cite{DeDoSc13}. %
Their answer to the question is to decompose the map $[ℓ]$ as a
composition of isogenies $\hat{ϕ}∘ϕ$, and then take the (irreducible)
polynomial vanishing on the fiber $ϕ^{-1}(P)$.

More precisely, let $\F_q$ be a finite field, and let $ℓ\nmid(q-1)$ be
odd and such that $ℓ\ll q+1+2\sqrt{q}$. %
Then there exists a curve $E$ which cardinality $\#E(\F_q)$ is
divisible by $\ell$. %
The hypothesis $ℓ\nmid(q-1)$ guarantees that $G = E[ℓ]∩E(\F_q)$ is
cyclic (see Exercise~\ref{ex:group-struct}). %
Let $ϕ$ be the degree $ℓ$ isogeny of kernel $G$, and let $E'$ be its
image curve. %
Let $P$ be a point in $E'(\F_q)\setminus [ℓ]E'(\F_q)$, Couveignes and
Lercier show that $\phi^{-1}(P)$ is an \emph{irreducible fiber}, i.e.,
that the polynomial
\[f(X) = \prod_{Q\in\phi^{-1}(P)}(X - x(Q))\]
is irreducible over $\F_q$.

To effectively compute the polynomial $f$, we need one last technical
ingredient: a way to compute a representation of the isogeny $ϕ$ as a
rational function. %
This is given to us by the famous V\'elu's formulas~\cite{velu71}.

\begin{proposition}[V\'elu's formulas]
  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 separable isogeny $ϕ:E\to 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}
\begin{proof}
  See~\cite[\S8.2]{df+thesis}.
\end{proof}

\begin{corollary}
  Let $E$ and $G$ be as above. %
  Let
  \[h(X) = \prod_{Q∈G\setminus\{\O\}}(X-x(Q)).\]
  Then the isogeny $ϕ$ can be expressed as
  \[ϕ(X,Y) = \left(\frac{g(X)}{h(X)}, y\left(\frac{g(x)}{h(x)}\right)'\right),\]
  where $g(X)$ is defined by
  \[\frac{g(X)}{h(X)} = dX-p_1-(3X^2+a)\frac{h'(X)}{h(X)}
    - 2(X^3+aX+b)\left(\frac{h'(X)}{h(X)}\right)',\]
  with $p_1$ the trace of $h(X)$ and $d$ its degree.
\end{corollary}
\begin{proof}
  See~\cite[\S8.2]{df+thesis}.
\end{proof}

\begin{figure}
  \begin{subfigure}{0.65\textwidth}
    \begin{algorithmic}[1]
      \REQUIRE A finite field $\F_q$,\\
      a prime power $ℓ^e$ such that $ℓ\nmid(q-1)$ and $ℓ\ll q$;
      \ENSURE An irreducible polynomial of degree $ℓ^e$.
      \STATE Take random curves $E_0$, until one with $ℓ|\#E_0$ is found;
      \STATE Factor $\#E_0$;
      \FOR {$1≤i≤e$}
      \STATE Use V\'elu's formulas to compute a degree $ℓ$ isogeny $ϕ_i:E_{i-1}\to E_i$;
      \ENDFOR
      \STATE Take random points $P\in E_i(\F_q)$ until one not in $[ℓ]E_i(\F_q)$ is found;
      \RETURN The polynomial vanishing on the abscissas of $ϕ_i^{-1}∘\cdots∘ϕ_1^{-1}(P)$.
    \end{algorithmic}
  \end{subfigure}
  %%
  \hfill
  %%
  \begin{subfigure}{0.2\textwidth}
    \begin{tikzpicture}
      \def\n{4}
      \foreach \i in {0,...,\n} {
        \pgfmathparse{360/(\n+1)*(\i-1/2) - 90}
        \let\angle\pgfmathresult
        \draw (\angle:1) node (E\i) {$E_\i$};
      }
      \foreach \i in {0,...,\n} {
        \pgfmathparse{int(mod(\i+1, \n+1))}
        \let\j\pgfmathresult
        \draw (E\i) edge[->,bend right=18] node[auto,swap] {\scriptsize$ϕ_\i$} (E\j);
      }
    \end{tikzpicture}
  \end{subfigure}
  
  \caption{Couveignes-Lercier algorithm to compute irreducible
    polynomials, and structure of the computed isogeny cycle.}
  \label{fig:CL}
\end{figure}

The Couveignes-Lercier algorithm is summarized in
Figure~\ref{fig:CL}. %
What is most interesting, is the fact that it can be immediately
generalized to computing irreducible polynomials of degree $ℓ^e$, by
iterating the construction. %
Looking at the specific parameters, it is apparent that $ℓ$ is an
\emph{Elkies prime} for $E$ (i.e., $\left(\frac{D}{ℓ}\right)=1$), and
that each isogeny $ϕ_i$ is horizontal, thus their composition
eventually forms a cycle, the \emph{crater} of a volcano.


\section{SIDH/SIKE, a defunct key exchange scheme}
\label{sec:sidh}

TODO

\begin{comment}

With CSIDH, we have seen 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 SIDH (Supersingular Isogeny
Diffie--Hellman)~\cite{jao+defeo2011,defeo+jao+plut12}, historically
the first practical isogeny based key exchange protocol.

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^{216}3^{137}-1$, $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 summarized in Figure~\ref{fig:sidh-prot}, and
schematized in Figure~\ref{fig:sidh}.

\begin{figure}
  \centering
  \begin{tabular}{l *{2}{p{32ex}<{\centering}}}
    \hline
    Public parameters & \multicolumn{2}{l}{Primes $ℓ_A,ℓ_B$, and a prime $p=ℓ_A^{e_A}ℓ_B^{e_B}f∓1$,}\\
                      & \multicolumn{2}{l}{A supersingular elliptic curve $E$ over $\F_{p^2}$ of order $(p±1)^2$,}\\
                      & \multicolumn{2}{l}{A basis $〈P_A,Q_A〉$ of $E[ℓ_A^{e_A}]$,}\\
                      & \multicolumn{2}{l}{A basis $〈P_B,Q_B〉$ of $E[ℓ_B^{e_B}]$,}\\
    \hline
                      & {\bf Alice} & {\bf Bob}\\
    \hline
    Pick random secret & $A=[m_A]P_A+[n_A]Q_A$ & $B=[m_B]P_B+[n_B]Q_B$\\[1ex]
    Compute secret isogeny & $α:E\to E_A=E/〈A〉$ & $β:E\to E_B=E/〈B〉$\\[1ex]
    Exchange data &  \hfill $E_A,α(P_B),α(Q_B) \longrightarrow$ & $\longleftarrow E_B,β(P_A),β(Q_A)$ \hfill\strut \\[1ex]
    Compute shared secret & $E/〈A,B〉 = E_B/〈β(A)〉$ & $E/〈A,B〉 = E_A/〈α(B)〉$
  \end{tabular}
  
  \caption{Supersingular Isogeny Diffie--Hellman key exchange protocol.}
  \label{fig:sidh-prot}
\end{figure}

\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}


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

\clearpage
\part{A personal history of isogeny based cryptography}

by Luca De Feo
\end{comment}

\end{document}

% Local Variables:
% ispell-local-dictionary:"american"
% End:

%  LocalWords:  Isogeny projective affine Abelian invertible isogeny
%  LocalWords:  isomorphism endomorphism endomorphisms isogenies
%  LocalWords:  cardinality automorphisms cryptographic cryptosystem
%  LocalWords:  parallelize homothety Homothetic invariants Expander
%  LocalWords:  supersingular irreducibility cryptographically torsor
%  LocalWords:  expander expanders Schreier coprime quaternion monic
% LocalWords:  morphisms bijection subring morphism surjective
% LocalWords:  discriminants homothetic Couveignes undirected