%%% =================================================
%%% @TeX-file{
%%% title = "Schoof-Elkies-Atkin Algorithm",
%%% version = "1.0",
%%% author = "Ben Galin",
%%% date = "2007/12/12",
%%% filename = "SchoofElkiesAtkinAlgorithm.tex",
%%% copyright = "Copyright 2007 Ben Galin.
%%% This work is licensed under the
%%% Creative Commons Attribution 2.5
%%% License. To view a copy of this
%%% license, visit
%%% http://creativecommons.org/
%%% licenses/by/2.5/
%%% or send a letter to
%%% Creative Commons,
%%% 543 Howard Street, 5th Floor,
%%% San Francisco,
%%% California, 94105, USA."
%%% }
%%% =================================================
\documentclass[11pt]{article}
\usepackage[margin=1.5in]{geometry}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{wasysym}
\usepackage{stmaryrd}
\usepackage{setspace}
\usepackage{url}
\usepackage{comment}
\usepackage{color}
\usepackage{float}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Projective}{\mathbb{P}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\Fp}{\F_p}
\newcommand{\Fpd}{\F_{p^d}}
\newcommand{\Fq}{\F_q}
\newcommand{\Fl}{\F_l}
\newcommand{\cFp}{\overline{\F}_p}
\newcommand{\cFq}{\overline{\F}_q}
\newcommand{\cFl}{\overline{\F}_l}
\DeclareMathOperator{\character}{char}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\SL}{SL}
\newcommand{\go}{\oplus}
\newcommand{\poi}{\mathcal{O}}
\newcommand{\Del}{\Delta}
\newcommand{\tj}{\tilde{\jmath}}
\newcommand{\tjp}{\mbox{$\tj\,$}^\prime}
\newcommand{\tjpp}{\mbox{$\tj\,$}^{\prime\prime}}
\newcommand{\PGL}{\mathrm{PGL}_2}
\newcommand{\euler}{\phi_{\mathrm{Eul}}}
\newcommand{\Endexample}{\hfill $\Diamond$}
\newcommand{\de}{\mathrm{d}}
\newcommand{\BB}{\mathfrak{B}}
\newcommand{\term}{\emph}
\newcommand{\eccpart}{\pagebreak\section}
\newcommand{\eccsection}{\subsection}
\newcommand{\eccsubsection}{\subsubsection}
\newcommand{\com}[1]{{\color{red}$*$}\marginpar{\raggedright \color{red} \small \sf #1}}
\newcommand{\tabspace}{\makebox[3em]{}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\begin{document}
%\onehalfspacing
\bibliographystyle{amsplain}
\title{Schoof-Elkies-Atkin Algorithm}
\date{December 12, 2007}
\author{Ben Galin\thanks{The author would like to express his sincere gratitude to his thesis advisor, Prof.\ Gunnar Carlsson, and his degree advisor, Prof.\ Dan Bump. \newline \newline This work is licensed under the Creative Commons Attribution 2.5 License. To view a copy of this license, visit \protect\url{http://creativecommons.org/licenses/by/2.5}. Source code with limited rights can be found at \protect\url{http://www.bens.ws/professional.php}.} \\ \url{bengalin@stanford.edu} \\ \ \\ Senior Thesis \\ Department of Mathematics \\ Stanford University}
\maketitle
\vfill
%=============================================
\eccpart{Introduction}\label{sec:Introduction}
%=============================================
Following a timeworn naming convention, we assume that two people, Alice and Bob, would like to communicate in a secure manner through an insecure channel. Their cryptographic goals can be summarized as follows \cite{Menezes-Handbook}:
\begin{enumerate}
\item \term{Confidentiality}: the content of the message is unknown to any third-party.
\item \term{Data integrity}: no third-party can change the content of the message in an undetected manner.
\item \term{Authentication}: a recipient of a message can detect the origin of the message.
\item \term{Non-repudiation}: a sender of a message cannot later deny the origin or content of a message.
\end{enumerate}
If Alice and Bob can agree somehow on a secret key, they may be able to encrypt their messages such that if Eve, an eavesdropper, is intercepting the communication, she would be unable to recover the original message or alter its content in an undetectable manner. This would satisfy the first two goals above. Assuming that this secret key is only known to Alice and Bob, it's a small stretch of the imagination to see how the other two goals can be satisfied.
A cryptosystem based on the property above is called \term{symmetric-key cryptography}. This is to be contrasted with \term{public-key cryptography}. Public-key cryptography owes it origin to the 1976 article by Diffie and Hellman \cite{Diffie-New}. It is based on the idea that each participant generates two keys, one private and one public. The public key $P_A$ of Alice is used by her partner, Bob, to encrypt a message he wishes to send to Alice. When Alice receives the ciphertext, she uses her private key $p_A$ to decrypt the message.
One of the main advantages of public-key cryptography is obvious: in a system of $n$ users, there is no need to distribute securely---and maintain the security of---$(n^2 - n)/2$ symmetric keys. Instead, each participant only needs access to the $n-1$ public keys of the other parties. However, one notable disadvantage of public-key cryptography in comparison to symmetric-key cryptography is that the latter allows a much faster encryption and decryption of messages \cite{Menezes-Handbook}.
In Section~\ref{sec:OverviewOfECC}, we provide the essential background information to a specific type of a public-key cryptosystem, known as the \term{Elliptic Curve Cryptography (ECC)}. The overview in that section is not meant to be comprehensive by any means; a reader with background in ECC would find the material insufficient and simplified. Instead, one should view Section~\ref{sec:OverviewOfECC} as a motivation to the rest of the discussion.
The focus of this paper is on the \texttt{SEA} algorithm, which is one of the leading algorithms for point-counting, a concept that will be defined later. In Section~\ref{sec:ArithmeticOfEllipticCurves}, we introduce and build on the mathematical foundation needed in discussing point-counting in general and the \texttt{SEA} algorithm in particular. The theory behind elliptic curves is rich and complex. Therefore, we find it essential to refer the reader to other sources when elementary proofs cannot be found.
Section~\ref{sec:SEAAlgorithm} includes the main exposition of this paper. It introduces Schoof's algorithm to determine the number of points on a curve, and then expands on this algorithm with Atkin's and Elkies' improvements. Once again, we shall occasionally encounter concepts that are beyond the scope of this paper and provide sources where proofs can be obtained. As elsewhere in modern cryptography, the mathematical theory is used to develop algorithms so that computations will be carried out by computers. To assist the reader in following this transition, we will work out a number of simple examples in an algorithmic fashion. We will conclude this section with a pseudo-code version of the \texttt{SEA} algorithm itself.
%=========================================================================
\eccpart{Overview of Elliptic Curve Cryptography}\label{sec:OverviewOfECC}
%=========================================================================
In this section we present an overview of ECC. We start by defining the Weierstrass equation of an elliptic curve and the group structure of the $K$-rational points of an elliptic curve, where $K$ is a finite field. We then introduce the \term{discrete logarithm problem (DLP)} cryptographic primitive and show how it is applied to ECC. To conclude, we present an implementation example, the \term{Elliptic Curve Digital Signature Algorithm (ECDSA)}.
\eccsection{Group structure}\label{sec:GroupStructure}
Let $K$ be a finite field, $K^*$ be its multiplicative group, and $\overline{K}$ be its algebraic closure. Our goal in this section is to first define elliptic curves and then construct a cyclic group $G$ corresponding to a given elliptic curve $E/K$. The group elements are a subset of the so-called $K$-rational points. Using projective coordinates, we shall see that an elliptic curve $E$ has one point of infinity, which we shall denote by $\poi$. We will endow the set of points on the curve with a group operation $\go$, such that $\poi$ is the identity element. Lastly, we will show that the $K$-rational points form a subgroup.
Following the treatment in \cite{Cohen-Handbook13}, we define an \term{elliptic curve $E$ over $K$} as follows:
\begin{definition}\label{def:EllipticCurve}
An \term{elliptic curve $E$ over a field $K$} is given by the affine Weierstrass equation
\begin{equation}\label{eq:Weierstrass}
E: y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6 \:,
\end{equation}
where the coefficients $a_i$ are in the underlying field $K$, and for each point $(x_1, y_1) \in \overline{K}$ satisfying Equation~\eqref{eq:Weierstrass}, the partial derivatives $3x_1^2 + 2a_2x_1 + a_4 - a_1y_1$ and $2y_1 + a_1x_1 + a_3$ do not vanish simultaneously.
\end{definition}
We write $E/K$ for an elliptic curve $E$ over $K$. When the underlying field is understood from the context, we may simply write $E$.
Let $E/K$ be an elliptic curve with a Weierstrass equation~\eqref{eq:Weierstrass}. Write its equation with homogeneous coordinates in the projective plane $\Projective^2(\overline{K})$ by setting $x = \frac{X}{Z}$ and $y = \frac{Y}{Z}$:
\begin{equation}\label{eq:HomogeneousWeierstrass}
Y^2Z + a_1XYZ + a_3YZ^2 = X^3 + a_2X^2Z + a_4XZ^2 + a_6Z^3 \:.
\end{equation}
With these homogeneous coordinates, the line of infinity is $Z = 0$. Thus, the intersection of the line of infinity with the elliptic curve $E$ yields the equation $X^3 = 0$ and a single point of infinity $[0,1,0]$. We denote this point of infinity by $\poi$. Note that the partial derivative of Equation~\eqref{eq:HomogeneousWeierstrass} with respect to $Z$ is $a_2X^2 + 2a_4XZ + 3a_6Z^2 - Y^2 - a_1XY - 2a_3YZ$, which does not vanish at $[0,1,0]$.
We say that a point $P = (x,y)$ is on an elliptic curve $E/K$ if its coordinates are a solution to the Weierstrass equation of $E$, which implies that $x$ and $y$ are in the algebraic closure $\overline{K}$ of $K$. Our next goal is to separate points $P$ on $E$ with coordinates in $K$ from the rest of the points.
\begin{definition}\label{def:RationalPoints}
Let $E/K$ be an elliptic curve. For any field $L$ with $K \subseteq L \subseteq \overline{K}$, an ordered pair $(x,y)$ is called an \term{$L$-rational point of $E$} if $x$ and $y$ lie in the field $L$ and $(x,y)$ is a solution to the Weierstrass equation of $E$. In addition, we define the point of infinity $\poi$ to be an $L$-rational point.
\end{definition}
The set of all $L$-rational points of $E$ is denoted by $E(L)$, and its cardinality is denoted by $|E(L)|$. We shall be mainly interested in $K$-rational points (that is, the case $L = K$).
Next, we define a group operation $\go$ on an elliptic curve $E/K$. First, we let $\poi$ be the identity element, so $\poi \go P = P \go \poi = P$ and $P \go - P = \poi$ for point $P$ on $E$. Let $P_1 = (x_1, y_1)$ and $P_2 = (x_2, y_2)$ be points on $E$. Then $P_1 \go P_2 = (x_3, y_3)$ with
\begin{align*}
-P_1 &= (x_1, -y_1 - a_1x_1 - a_3) \:, \\
P_1 \go P_2 &= \left(\lambda^2 + a_1\lambda - a_2 - x_1 - x_2, \lambda(x_1 - x_3) - y_1 - a_1x_3 - a_3\right)\:, \text{where} \\
\lambda &=
\begin{cases} \vspace{1em}
\displaystyle \frac{y_1 - y_2}{x_1 - x_2} & \text{if } P_1 \neq \pm P_2 \:, \\
\displaystyle \frac{3x_1^2 + 2a_2x_1 + a_4 - a_1y_1}{2y_1 + a_1x_1 + a_3} & \text{if } P_1 = P_2 \:.
\end{cases}
\end{align*}
Proving that $(E/K, \go)$ is indeed a group is a straightforward process, albeit a tedious one. The associative rule, in particular, is painful. The group $(E/K, \go)$ is, in fact, abelian: Let $P_2 \go P_1 = (x_4, y_4)$ and observe that $\frac{y_1 - y_2}{x_1 - x_2} = \frac{y_2 - y_1}{x_2 - x_1}$, so $\lambda$ is invariant. Then
\begin{align*}
x_3 &= \lambda^2 + a_1\lambda - a_2 - x_1 - x_2 = x_4 \:, \\
y_3 &= \lambda(x_1 - x_3) - y_1 - a_1x_3 - a_3 = \lambda(x_2 - x_3) + \lambda(x_1 - x_2) - y_1 - a_1x_3 - a_3 \\
&= \lambda(x_2 - x_3) - y_2 - a_1x_3 - a_3 = y_4 \:.
\end{align*}
We have defined a group operation on the entire set of points $P$ on an elliptic curve $E/K$. However, we shall be mainly interested in $K$-rational points. From the definition of $\go$, it is clear that if $P_1$ and $P_2$ are $K$-rational points, then so are $P_1 \go P_2$ and $-P_1$, so $(E(K), \go)$ is indeed a subgroup of $(E/K, \go)$.
Henceforth, we shall write $E/K$ and $E(K)$ in favor of $(E/K, \go)$ and $(E(K), \go)$, respectively, for the groups.
\eccsection{Discrete logarithm problem}\label{sec:DiscreteLogarithmProblem}
In this section we begin relating the concepts defined above with the field of elliptic curve cryptography. The following definition is the cornerstone of ECC.
\begin{definition}\label{def:ScalarMultiplication}
Let $E/K$ be an elliptic curve. We define the \term{scalar multiplication by $n$}, where $n$ is a positive integer, as a function
\begin{align*}
[n]: E/K &\to E/K \\
P &\mapsto [n]P = \underset{n \text{ times}}{\underbrace{P \go \cdots \go P}} \:.
\end{align*}
We extend this definition to all integers $n$ by defining $[0]P = \poi$ and $[n]P = [-n](-P)$ for $n < 0$. Note that if $P$ is a $K$-rational point, than so is $[n]P$. Thus, the restriction of $[n]$ to the subgroup of $K$-rational points $E(K)$, yields a map $[n]: E(K) \to E(K)$.
\end{definition}
We build on Definition~\ref{def:ScalarMultiplication} to introduce the district log problem, which is most commonly applied on cyclic groups of prime order. Note however that the group of $K$-rational points $E(K)$ need not be a cyclic group. In the remainder, we will let $G$ be a cyclic subgroup of $E(K)$ of some prime order $l$.
\begin{definition}\label{def:DiscreteLogarithm}
Let $G \leq E(K)$ be a group of prime order $l$, and let $P, Q \in G$ with $P \neq \poi$. Then the \term{discrete logarithm of $Q$ with respect to $P$} is an integer $n$ such that $Q = [n]P$.
\end{definition}
Note that computing the discrete logarithm $n$ can be done, and is unique, modulo $l$. The problem of finding the discrete logarithm of $Q$ with respect to $P$ for an arbitrary pair of elements $P, Q \in G$ is called the \term{discrete logarithm problem (DLP) in $G$}.
As explained by Avanzi \cite{Cohen-Handbook19}, the complexity of solving the DLP in $G$ is determined by the structure and representation of $G$. For instance, Lagrange's theorem asserts that there is only one group, up to isomorphism, of prime order $l$, so the DLP in $G$ can be transformed to the one in $(\Z/l\Z, +)$. On the other hand, $G$ can be embedded into the multiplicative group of $\F_r$ as the group of $l$-th roots of unity, where $l$ divides $r-1$. However, Avanzi \cite{Cohen-Handbook19} shows that the DLP in this group is harder than in $(\Z/l\Z, +)$.
In general, the DLP is considered a hard problem to solve for many finite cyclic groups of large order, though much care should be practiced in choosing the exact group. As such, the DLP is used as a \term{cryptographic primitive}, and a number of DLP-based cryptosystems have emerged. Examples of such cryptosystems are the ElGamal encryption, the Diffie-Hellman key exchange, and the elliptic curve digital signature algorithm systems. The last systems is discussed in some more detail in Section~\ref{sec:ImplementationExample}.
\eccsection{Security of ECC}\label{sec:SecurityOfECC}
With a careful choice of an elliptic curve $E$, an underlying field $K$, and the cyclic subgroup $G \leq E(K)$, the corresponding elliptic curve cryptosystem can provide the same level of security as the integer-factorization based system RSA, while allowing significantly smaller key sizes \cite{Vercauteren-SEA}.
A standard way of assessing the level of security provided by a cryptosystem is to determine complexity of the best known attack algorithm against it \cite{Cohen-Handbook1}. Here, complexity is defined as follows:
\begin{definition}\label{def:Complexity}
Let $\texttt{Alg}$ be an algorithm depending on $N$. Define
\begin{equation*}
L_N(\alpha, c) = \exp\left(c(\ln N)^\alpha(\ln \ln N)^{1-\alpha}\right) \:,
\end{equation*}
where $0 \leq \alpha \leq 1$ and $c > 0$. Then \texttt{Alg} is said to be \term{exponential in $N$} if its running time is bounded from above by a function proportional to $L_N(1, c)$; it is \term{polynomial in $N$} if its running time is bounded from above by a function proportional to $L_N(0, c)$; and it is \term{subexponential in $N$} if its running time is bounded from above by a function proportional to $L_N(\alpha, c)$ for $\alpha < 1$.
\end{definition}
Note that the designation \textit{exponential} refers to exponential in the \textit{logarithm} of the order. In other words, an exponential algorithm in the group order $|G|$ is one that requires no more than $|G|^C$ group compositions, where $C$ is a positive constant. It is known \cite{Cohen-Handbook19}, that for any cyclic group we have $C \leq 1/2$.
As discussed in \cite{Cohen-Handbook19}, \cite{Menezes-Handbook}, and \cite{Lopez-Overview}, at present there are no generic subexponential algorithms to solve the DLP, where a generic algorithm is defined to be one which only performs composition, inversion, and equality checking. Examples of generic algorithms are the Chinese remainder theorem (CRT), Pollard's rho method, and the baby-step/giant-step (BSGS) algorithm. We will see an algorithm related to the BSGS algorithm in Section~\ref{sec:CombiningInformation}.
For curves with additional properties, some of which will be described later, there are subexponential algorithms that may be used to solve the DLP, such as the index calculus attack and Weil descent. We invite the reader to refer to the excellent surveys by Avanzi and Th\'{e}riault \cite{Cohen-Handbook20} and Frey and Lange \cite{Cohen-Handbook22} for more details about different algorithms, as well as additional references.
In Table~\ref{tab:KeySizeComparison}, adapted from the National Institute of Standards and Technology publication \cite{NIST-Recommendation}, we provide a comparison of key sizes between (i) finite field cryptography (FFC), such as Diffie-Hellmand key exchange and DSA; (ii) integer-factorization cryptography (IFC), such as RSA; and (iii) elliptic curve cryptography (ECC), such as ECDSA, which will be explained in Section~\ref{sec:ImplementationExample}.
\begin{table}[H]
\centering
\begin{tabular}{c|c|c|c}
Bits of security & FFC & IFC & ECC \\ \hline
80 & 1024 for public, 160 for private & 1024 & 160--223 \\
112 & 2048 for public, 224 for private & 2048 & 224-255 \\
128 & 3072 for public, 256 for private & 3072 & 256--383 \\
192 & 7680 for public, 384 for private & 7680 & 384--511 \\
256 & 15360 for public, 512 for private & 15360 & 512+
\end{tabular}
\caption{Comparison of key sizes\label{tab:KeySizeComparison}}
\end{table}
The reason for the striking difference in key sizes between ECC and the other two leading cryptosystems is that there are known subexponential algorithms to break FFC and IFC systems (see \cite{Cohen-Handbook1} and \cite{Lopez-Overview}). Therefore, in order to achieve the same level of security, one needs shorter keys when using an ECC-based system in comparison to RSA or non ECC-based DLP systems. This represents a significant advantage of ECC over other systems when hardware resources are limited.
\eccsection{Implementation example: ECDSA}\label{sec:ImplementationExample}
In this section we provide an example for an elliptic curve cryptosystem implementation.
Specifically, we describe the \term{Elliptic Curve Digital Signature Algorithm (ECDSA)}, which is an ElGamal-like digital signature algorithm, based on ECC. A digital signature algorithm is comprised of two separate algorithms, one for signing a message by the sender and the other for verifying the signature by the recipient. In the first algorithm, Alice, the sender, appends to a message $m$ a signature $(r, s)$ that depends on her private key $p_A$ and the content of the message itself. Bob, the recipient, verifies the signature, using the knowledge of Alice's public key $P_A$.
In the context of elliptic curve cryptosystems, we define the following tuple of domain parameters $D = (q, \textit{FR}, a_4, a_6, P, l, c)$:
\begin{itemize}
\item $q$ is the field characteristic;
\item $\textit{FR}$ is a field representation of $\Fq$;
\item $a_4$ and $a_6$ are the coefficients of the short Weierstrass equation of $E$, an elliptic curve over $\Fq$;
\item $P = (x_P, y_P)$ is an $\Fq$-rational base point;
\item $l$ is the order of a prime cyclic subgroup of $\Fq$, which contains $P$; and
\item $c = |E(\Fq)|/l$.
\end{itemize}
We shall assume that the domain parameters are known to all parties and possibly to intruders, as well.
We present the digital signature algorithm in the context of ECC, as adapted from \cite{Lopez-Overview}. A simple key generation algorithm is presented in Figure~\ref{alg:GenerateKey}. This algorithm is based on the difficulty to solve the discrete log problem in the group of $\Fq$-rational points. The algorithm in Figure~\ref{alg:SignatureECDSA} describes the signature procedure of ECDSA, and the algorithm in Figure~\ref{alg:VerificationECDSA} illustrates the verification procedure. We assume that both parties have agreed on a hash function $h$, where we recall from \cite{Cohen-Handbook1} that a hash function $h: S \to T$ is a function that is
\begin{enumerate}
\item \term{Pre-image resistant}, in the sense that for almost all $t \in T$ it is computationally infeasible to find $s \in S$ such that $h(s) = t$;
\item \term{Second pre-image resistant}, in the sense that for any $s_1 \in S$ it is computationally infeasible to find $s_2 \in S$ such that $h(s_1) = h(s_2)$; and
\item \term{Collusion resistant}, in the sense that it is computationally infeasible to find distinct $s_1, s_2 \in S$ such that $h(s_1) = h(s_2)$.
\end{enumerate}
It is important to note that the algorithms we present are not ready for use as-is. For instance, in the key generation algorithm we allow $p_A = 1$, which is clearly not desirable. A comprehensive specification can be obtained from the ANSI X9.62 standard \cite{ANSI-Public}.
\begin{figure}[H] \hrule \ \\ \sf
\texttt{GenerateKey}$(D)$ \\
Input: The domain parameters $D$. \\
Output: A private key $p_A$ and a public key $P_A$. \hrule
\begin{tabbing}
\phantom{0}1. \quad select a random integer $p_A \in [1, l-1]$ \\
\phantom{0}2. \quad $P_A \leftarrow [p_A]P$ \\
\phantom{0}3. \quad \textbf{return} $p_A$ and $P_A$
\end{tabbing} \hrule \rm
\caption{ECC key generation\label{alg:GenerateKey}}
\end{figure}
\begin{figure}[H] \hrule \ \\ \sf
\texttt{SignatureECDSA}$(D, h, p_A, m)$ \\
Input: The domain parameters $D$, a hash function $h$, the sender's private key $p_A$, and a message $m$. \\
Output: A signature $(r, s)$ on the message $m$. \hrule
\begin{tabbing}
\phantom{0}1. \quad select a random integer $k \in [1, l-1]$ \\
\phantom{0}2. \quad $(x_1, y_1) \leftarrow [k]P$ \\
\phantom{0}3. \quad $r \leftarrow x_1 \mod{l}$ \\
\phantom{0}4. \quad \textbf{if} $r = 0$ \textbf{then go to} step 1 \\
\phantom{0}5. \quad $s \leftarrow k^{-1}(h(m) + p_Ar)) \mod{l}$ \\
\phantom{0}6. \quad \textbf{if} $s = 0$ \textbf{then go to} step 1 \\
\phantom{0}7. \quad \textbf{return} $(r,s)$
\end{tabbing} \hrule \rm
\caption{ECDSA signature\label{alg:SignatureECDSA}}
\end{figure}
\begin{figure}[H] \hrule \ \\ \sf
\texttt{VerificationECDSA}$(D, h, P_A, m, (r,s))$ \\
Input: The domain parameters $D$, a hash function $h$, the sender's public key $P_A$, a message $m$, and a signature $(r,s)$ on $m$. \\
Output: \textbf{true} if $(r,s)$ is a valid signature of $m$, \textbf{false} otherwise. \hrule
\begin{tabbing}
\phantom{0}1. \quad \textbf{if} $r, s \notin [1, l-1]$ \textbf{then return false} \\
\phantom{0}2. \quad $(x_1, y_1) \leftarrow [h(m)s^{-1}]P \go [rs^{-1}]P_A$ \\
\phantom{0}3. \quad \textbf{if} $x_1 \equiv r \pmod{l}$ \textbf{then return true} \\
\phantom{0}4. \quad \textbf{return false}
\end{tabbing} \hrule \rm
\caption{ECDSA verification\label{alg:VerificationECDSA}}
\end{figure}
The verification algorithm return the correct resolution, as can be verified by
\begin{align*}
(x_1, y_1) &= [h(m)s^{-1}]P \go [rs^{-1}]P_A = \left[{\textstyle \frac{h(m)k}{h(m) + p_Ar}}\right]P \go \left[{\textstyle \frac{rk}{h(m) + p_Ar}}\right]P_A \\
&= \left[{\textstyle \frac{h(m)k}{h(m) + p_Ar}}\right]P \go \left[{\textstyle \frac{p_Ark}{h(m) + p_Ar}}\right]P = \left[{\textstyle \frac{k\left(h(m) + p_Ar\right)}{h(m) + p_Ar}}\right]P = [k]P \:,
\end{align*}
as needed.
%============================================================================
\eccpart{Arithmetic of Elliptic Curves}\label{sec:ArithmeticOfEllipticCurves}
%============================================================================
In this section we examine properties of elliptic curves that are essential in the development of the \texttt{SEA} algorithm. Our first step is to introduce a shorter form of the Weierstrass equation. To that end, we will define curve isomorphisms and survey some of their properties. Curve isomorphism and the scalar multiplication maps are special cases of curve isogenies, which we shall introduce next. Towards the end of this section, we will take a detour into the beautiful theory of complex analysis as a prelude to defining the division and modular polynomials. This will equip us with all the necessary tools before taking a stab at the \texttt{SEA} algorithm.
\eccsection{Isomorphism and short Weierstrass equations}\label{sec:IsomorphismAndShortWeierstrassEquations}
Let $K$ be a finite field and $E/K$ be an elliptic curve with the Weierstrass equation
\begin{equation}
E: y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6 \:. \tag{\ref{eq:Weierstrass}}
\end{equation}
We wish to associate to $E$ two constants: the discriminant and the absolute invariant (also called the $j$-invariant). To that end, it is useful to introduce the following constants:
\begin{equation}\label{eq:EllipticConstants}
\left.
\begin{aligned}
b_2 &= a_1^2 + 4a_2 \:, \quad b_4 = 2a_4 + a_1a_3 \:, \quad b_6 = a_3^2 + 4a_6 \:, \\
b_8 &= a_1^2a_6 - a_1a_3a_4 + 4a_2a_6 + a_2a_3^2 - a_4^2 = (b_2b_6 - b_4^2)/4 \:, \\
c_4 &= b_2^2 - 24b_4 \:, \quad c_6 = -b_2^3 + 36b_2b_4 - 216b_6 \:.
\end{aligned}
\right.
\end{equation}
Then we have the following definition:
\begin{definition}\label{def:DiscriminantAndAbsoluteInvariant}
Let $E$ be an elliptic curve with a Weierstrass equation~\eqref{eq:Weierstrass}. The \term{discriminant} of $E$ is $\Del_E = -b_2^2b_8 - 8b_4^3 - 27b_6^2 + 9b_2b_4b_6$. If $\Del_E = 0$ we say that $E$ is \term{singular}. Otherwise, we define the \term{absolute invariant}, or \term{$j$-invariant}, of $E$ to be $j(E) = j_E = c_4^3/\Del_E$.
\end{definition}
In the context of the \texttt{SEA} algorithm, we are particularly interested in fields of characteristic greater than 3. Note that by definition we have
\begin{align*}
c_4^3 &= b_2^6 - 72 b_2^4 b_4 + 1728 b_2^2 b_4^2 - 13824 b_4^4 \:, \\
c_6^2 &= b_2^6 - 72 b_2^4 b_4 + 1296 b_2^2 b_4^2 + 432 b_2^3 b_6 - 15552 b_2 b_4 b_6 + 46656 b_6^2 \:.
\end{align*}
So when the field characteristic is prime to 6 we may divide by $2^63^3 = 1728$ and write
\begin{equation*}
\Del_E = -b_2^2b_8 - 8b_4^3 - 27b_6^2 + 9b_2b_4b_6 = \frac{c_4^3 - c_6^2}{1728} \:.
\end{equation*}
The definition of the $j$-invariant leads us to the closely related notion of elliptic curve isomorphism. We shall call two curves isomorphic (over a certain field) if there is an admissible change of variables from one curve to the other. More specifically, we have
\begin{definition}\label{def:Isomorphism}
Let $L$ be a field extension $K \subseteq L \subseteq \overline{K}$. Two elliptic curves $E_1/K$ (with variables $x_1$ and $y_1$) and $E_2/K$ (with variables $x_2$ and $y_2$) are said to be \term{isomorphic elliptic curves over $L$} (or \term{$L$-isomorphic}) if there exists an element $(r,s,t,u) \in L^3 \times L^*$, such that the change of variable maps
\begin{align*}
x_1 &\mapsto u^2x_2 + r \:, & y_1 &\mapsto u^3y_2 + u^2sx_2 + t \:, & \poi_1 &\mapsto \poi_2
\end{align*}
transform $E_1/K$ to $E_2/K$. Such transformations are called \term{admissible change of variables}, or \term{$L$-isomorphisms}. By convention, we take the transformation $\poi_1 \mapsto \poi_2$ for granted and do not mention it explicitly.
\end{definition}
Note that these transformations are invertible with the inverse transformations being
\begin{align*}
x_2 &\mapsto \left(u^{-1}\right)^2x_1 + \left[- \left(u^{-1}\right)^2r\right] \quad \text{and} \\
y_2 &\mapsto \left(u^{-1}\right)^3y_1 + \left(u^{-1}\right)^2\left[u^{-1}s\right]x_1 + \left[\left(u^{-1}\right)^3(sr-t)\right] \:.
\end{align*}
Thus, we have shown that isomorphism of curves is a symmetric relation. Furthermore, it is also a transitive relation: suppose we have $(r_1,s_1,t_1,u_1), (r_2,s_2,t_2,u_2) \in K^3 \times K^*$, such that the change of variable maps
\begin{align*}
x_i &\mapsto u_i^2x_{i+1} + r &&\text{and} & y_i &\mapsto u_i^3y_{i+1} + u_i^2s_ix_{i+1} + t_i
\end{align*}
transform $E_i/K$ to $E_{i+1}/K$, $i = 1, 2$. Then
\begin{align*}
x_1 &= \left(u_1u_2\right)^2x_3 + \left[u_1^2r_2 + r_1\right] \quad \text{and} \\
y_1 &= \left(u_1u_2\right)^3y_3 + \left(u_1u_2\right)^2\left[u_1s_2 + s_1\right]x_3 + \left[u_1^3t_2 + u_1^2s_1r_2 + t_1\right]
\end{align*}
transform $E_1/K$ to $E_3/K$. Since reflexivity is trivial, we have established that isomorphism of curves is an equivalence relation.
Before we continue with more results regarding elliptic curve isomorphism, we find the next detour beneficial. Recall the Weierstrass equation
\begin{equation}
E: y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6 \:. \tag{\ref{eq:Weierstrass}}
\end{equation}
It is desirable to transform this equation to a simpler form. This is admissible using elliptic curve isomorphisms, as defined in Definition~\ref{def:Isomorphism}. The final form, however, depends on the characteristic of the underlying field $K$. The following lemma deals with the case of $\character(K) = p > 3$. There exist similar statements for the cases $p = 2$ and $p = 3$, but since the \texttt{SEA} algorithm is mostly used over large prime fields, the following suffices to our purpose.
\begin{lemma}\label{thm:ShortWeierstrassEquation}
Let $K$ be a finite field with $\character{K} = p > 3$, and let $E/K$ be an elliptic curve with a Weierstrass equation given in~\eqref{eq:Weierstrass}. There exists an $K$-isomorphic curve $E'/K$ (in variables $x'$ and $y'$) to $E$ with the following short Weierstrass equation
\begin{equation*}
E': (y')^2 = (x')^3 + \tilde{a}_4x' + \tilde{a}_6 \:,
\end{equation*}
where the coefficients $\tilde{a}_4$ and $\tilde{a}_6$ are in $K$.
\end{lemma}
\begin{proof}
Consider the following transformation:
\begin{align*}
x &\mapsto x' - \left(\frac{a_1^2 + 4a_2}{12}\right) \:, & y &\mapsto y' - \left(\frac{a_1}{2}\right)x' + \left(\frac{a_1^3 + 4a_1a_2 - 12a_3}{24}\right) \:.
\end{align*}
Then the Weierstrass equation of $E'$ becomes
\begin{align*}
(y')^2 &= (x')^3 - \left(\frac{a_1^4 + 8a_1^2a_2 - 24a_1a_3 + 16a_2^2 - 48a_4}{48}\right)x' + \left(\frac{a_1^6 + 12a_1^4a_2 - 36a_1^3a_3}{864}\right) \\
& \quad + \left(\frac{48a_1^2a_2^2 - 72a_1^2a_4 - 144a_1a_2a_3 + 64a_2^3 - 288a_2a_4 + 216a_3^2 + 864a_6}{864}\right) \:,
\end{align*}
as needed.
\end{proof}
For simplicity, we shall immediately change notation and write the short Weierstrass equation as
\begin{equation}\label{eq:ShortWeierstrass}
E: y^2 = x^3 + a_4x + a_6 \:.
\end{equation}
Through the remainder of this paper, we will only treat elliptic curves in their short Weierstrass equation form. This form allows much simpler expressions for the discriminant, $j$-invariant, and group law associated with an elliptic curve. We start by writing the constants in Equation~\eqref{eq:EllipticConstants} in terms of the coefficients of the short Weierstrass equation:
\begin{equation*}
\left.
\begin{aligned}
b_2 &= 0 \:, \quad b_4 = 2a_4 \:, \quad b_6 = 4a_6 \:, \quad b_8 = -a_4^2 \:, \\
c_4 &= -48a_4 \:, \quad c_6 = -864a_6 \:.
\end{aligned}
\right.
\end{equation*}
Consequently, the discriminant of $E$ is $\Del_E = -64a_4^3 - 432a_6^2$ and the $j$-invariant of $E$ is
\begin{equation}\label{eq:ShortJInvariant}
j_E = 1728\left(\frac{4a_4^3}{4a_4^3 + 27a_6^2}\right) \:.
\end{equation}
The group law of an elliptic curve given by a short Weierstrass equation becomes
\begin{equation}\label{eq:ShortGroupLaw}
\left.
\begin{aligned}
-P_1 &= (x_1, -y_1) \:, \\
P_1 \go P_2 &= (x_3, y_3) = \left(\lambda^2 - x_1 - x_2, \lambda(x_1 - x_3) - y_1\right)\:, \text{where} \\
\lambda &=
\begin{cases} \vspace{1em}
\displaystyle \frac{y_1 - y_2}{x_1 - x_2} & \text{if } P_1 \neq \pm P_2 \:, \\
\displaystyle \frac{3x_1^2 + a_4}{2y_1} & \text{if } P_1 = P_2 \:.
\end{cases}
\end{aligned}
\right.
\end{equation}
In addition, the only admissible changes of variables that preserve the short Weierstrass form are
\begin{align*}
x_1 &\mapsto u^2x_2 &&\text{and} & y_1 &\mapsto u^3y_2
\end{align*}
for some $u \in \overline{K}^*$.
We continue our discussion with more results related to elliptic curve isomorphism. The following important proposition shows that $j$-invariants of curves $E/K$ classify the isomorphism classes over the algebraic closure $\overline{K}$.
\begin{proposition}\label{thm:AbsoluteInvariantIsomorphism}
Let $E/K$ and $E'/K$ be two elliptic curves. If $E$ and $E'$ are isomorphic over $K$ then they have the same $j$-invariant. Conversely, if $E$ and $E'$ have the same $j$-invariants then the two curves are isomorphic over $\overline{K}$.
\end{proposition}
\begin{proof}
We shall prove the theorem only for the case $\character(K) = p > 3$, which is the only case where the \texttt{SEA} algorithm is applied in practice. Let $E/K$ be an elliptic curve given by the short Weierstrass equation
\begin{align*}
E/K: y_1^2 = x_1^3 + a_4x_1 + a_6 \:.
\end{align*}
Suppose that there exists a $K$-isomorphism given by $x_1 \mapsto u^2x_2$ and $y_1 \mapsto u^3y_2$, where $u \in K^*$, from $E/K$ to an isomorphic elliptic curve
\begin{align*}
\tilde{E}/K: y_2^2 = x_2^3 + \tilde{a_4}x_2 + \tilde{a_6} \:.
\end{align*}
Then one sees that $\tilde{a_4} = a_4/(u^4)$ and $\tilde{a_6} = a_6/(u^6)$. Consequently, we have $\tilde{c_4} = c_4/(u^4)$ and $\tilde{c_6} = c_6/(u^6)$. It follows that $\Del_{\tilde{E}} = \Del_E/(u^{12})$, so that the two curves have the same $j$-invariant, as needed.
Conversely, suppose the curve $E/K$ and $\tilde{E}/K$ have the same $j$-invariant. That is, we have
\begin{align*}
1728\left(\frac{4a_4^3}{4a_4^3 + 27a_6^2}\right) = 1728\left(\frac{4\tilde{a_4}^3}{4\tilde{a_4}^3 + 27\tilde{a_6}^2}\right) \:.
\end{align*}
Therefore, $a_4^3\tilde{a_6}^2 = \tilde{a_4}^3a_6^2$. We consider three cases:
\begin{enumerate}
\item $a_4 = 0$. Then since $\Del_E \neq 0$ we must have $a_6 \neq 0$. It follows that $\tilde{a_4} = 0$ and $\tilde{a_6} \neq 0$. Let $u = (a_6/\tilde{a_6})^{1/6}$ and note that the admissible change of variables $x_1 \mapsto u^3x_2$ and $y_1 \mapsto u^2y_2$ takes $E$ to $\tilde{E}$.
\item $a_6 = 0$. Then similar to before we have $a_4 \neq 0$, $\tilde{a_6} = 0$ and $\tilde{a_4} \neq 0$. Let $u = (a_4/\tilde{a_4})^{1/4}$ and again the admissible change of variables $x_1 \mapsto u^3x_2$ and $y_1 \mapsto u^2y_2$ takes $E$ to $\tilde{E}$.
\item $a_4a_6 \neq 0$. Then, also using $\Del_{\tilde{E}} \neq 0$, we must have $\tilde{a_4}\tilde{a_6} \neq 0$. Let $u = (a_4/\tilde{a_4})^{1/4} = (a_6/\tilde{a_6})^{1/6}$, so the admissible change of variables $x_1 \mapsto u^3x_2$ and $y_1 \mapsto u^2y_2$ takes $E$ to $\tilde{E}$.
\end{enumerate}
This concludes the proof.
\end{proof}
In the context of ECC, the above definition of isomorphism over $K$ of curves would have been of little significance if this isomorphism did not respect the group operation on the $K$-rational points. The following proposition establishes that if $E/K$ and $E'/K$ are isomorphic curves, then $E(K)$ and $E'(K)$ are indeed homomorphic as groups.
\begin{proposition}\label{thm:CurveIsomorphismImpliesGroupHomomorphism}
Let $E/K$ and $E'/K$ be $K$-isomorphic curves. Then the groups of $K$-rational points $E(K)$ and $E'(K)$ are homomorphic.
\end{proposition}
\begin{proof}
We prove the proposition only for the case $\character(K) = p > 3$. Let
\begin{align*}
E: y^2 &= x^3 + a_4x + a_6 && \text{and} &
\tilde{E}: \tilde{y}^2 &= \tilde{x}^3 + \tilde{a_4}\tilde{x} + \tilde{a_6}
\end{align*}
be $K$-isomorphic curves, where the isomorphism $\theta$ is given by $x \mapsto u^2\tilde{x}$ and $y \mapsto u^3\tilde{y}$ for some $u \in K^*$. By a slight abuse of notation, we overload $\theta$ and let it act on points on the curve $E$, as well as expressions involving the variables $x$ and $y$. Let $P_1 = (x_1, y_1)$ and $P_2 = (x_2, y_2)$ be two $K$-rational points of $E$. We clearly have
\begin{align*}
\theta(-P_1) &= \theta(x_1, -y_1) = (u^2\tilde{x_1}, -u^3\tilde{y_1}) = -\theta(P_1) \:. \end{align*}
Define $\tilde{\lambda}$ for $\tilde{E}$ in analogous way to Equation~\eqref{eq:ShortGroupLaw}. Then manipulating the expression for $\tilde{\lambda}$, we see that $\theta(\lambda) = u\tilde{\lambda}$, regardless of whether $P_1 = P_2$ or not. It follows that
\begin{align*}
\theta(P_1 \go P_2) &= \theta\left( \lambda^2 - x_1 - x_2 \:, \lambda\left(2x_1 + x_2 - \lambda^2\right) - y_1 \right) \\
&= \left( u^2 \left[\bigl(\tilde{\lambda}\bigr)^2 - \tilde{x_1} - \tilde{x_2} \right] \:, u^3 \left[ \tilde{\lambda}\left(2\tilde{x_1} + \tilde{x_2} - \bigl(\tilde{\lambda}\bigr)^2\right) - \tilde{y_1}\right] \right) \\
&= \theta(P_1) \go \theta(P_2) \:.
\end{align*}
This proves the proposition.
\end{proof}
\eccsection{Isogenies}\label{sec:Isogenies}
In Proposition~\ref{thm:CurveIsomorphismImpliesGroupHomomorphism} we showed that $K$-isomorphic curves have homomorphic groups of $K$-rational points. However, isomorphism of elliptic curves is a much more restrictive notion than homomorphism of the respective groups of $K$-rational points. In this section we define isogenies and survey some of their properties, not the least of which is preserving the group structure of the $K$-rational points. Given the rich theory in which isogenies arise, we only state basic results in this section and do not provide proofs. An excellent introduction to isogenies, focusing on elliptic curves, is Silverman \cite{Silverman-Arithmetic}. More information can be found in Cassels' study \cite{Cassels-Diophantine}.
We start with a few definitions.
\begin{definition}\label{def:Isogeny}
Let $E/K$ and $E'/K$ be two elliptic curves.
\begin{enumerate}
\item A \term{morphism} from $E$ to $E'$ is a rational map with coefficients in $K$ which is regular at every point of $E$.
\item An \term{isogeny} from $E$ to $E'$ is a morphism $\psi: E \to E'$ that is (i) a nonconstant morphism mapping $\poi_E$ to $\poi_{E'}$, or (ii) the zero-morphism $P \mapsto \poi_{E'}$ for all $P \in E$. Two elliptic curves $E/K$ and $E'/K$ are said to be \term{isogenous} if such an isogeny $\psi: E \to E'$ exists. The \term{degree} of an isogeny $\psi$ is the cardinality of its kernel.
\item An isogeny $\psi$ from $E$ to itself is called an \term{endomorphism} of $E$. The set of all endomorphism of $E$ is denoted by $\End_K(E)$, or simply $\End(E)$ when the field is understood from the context.
\end{enumerate}
\end{definition}
In fact, the notion of an isogeny is not new to us; curve isomorphisms are the simplest type of isogenies between curves, and the scalar multiplication maps we saw in Definition~\ref{def:ScalarMultiplication} are isogenies from a curve to itself. However, the theory of general isogenies is deeper, owing much of its beauty to the following observation: if $\psi$ is an isogeny of curves from $E_1/K$ to $E_2/K$, then it induces an injection of function fields $\psi^*: \overline{K}(E_2) \hookrightarrow \overline{K}(E_1)$. The degree of $\psi$---as well as the definition of whether $\psi$ is separable, inseparable, or purely inseparable---are determined by the field extension $\overline{K}(E_1)/\psi^*\overline{K}(E_2)$. This observation leads to the following important theorem:
\begin{theorem}\label{thm:IsogenyRationalPoints}
Let $E/K$ and $E'/K$ be isogenous elliptic curves over $K$ under the isogeny $\psi$. Then $\psi$ is a group homomorphism from $E(K)$ to $E'(K)$.
\end{theorem}
\begin{proof}
See \cite[pages 75--76]{Silverman-Arithmetic}.
\end{proof}
Like curve isomorphism, curve isogeny is also an equivalence relation. We don't provide the details here, but only state that the symmetric property is given by the so-called dual isogeny. This and other basic properties of isogenies are given in the next proposition.
\begin{proposition}\label{thm:BasicPropertiesOfIsogenies}
Let $\psi: E_1/K \to E_2/K$ be a non-constant isogeny of degree $m$.
\begin{enumerate}
\item For every $P \in E_2$, we have $|\psi^{-1}(P)| = \deg_s\psi$, where $\deg_s\psi$ is the separable degree of $\psi$.
\item There is a unique dual isogeny $\hat{\psi}: E_2/K \to E_1/K$ such that $\hat{\psi} \circ \psi = [m]$ on $E_1$ and $\psi \circ \hat{\psi} = [m]$ on $E_2$. Here, $\circ$ is the composition of morphisms operation. We extend this to the case that $\psi$ is the constant (zero) isogeny by taking $\hat{\psi}$ to also be the constant isogeny.
\item $\deg \psi = \deg \hat{\psi}$.
\end{enumerate}
Let $n$ be an integer
\begin{enumerate}
\item[4.] The degree of the endomorphism $[n]$ is $n^2$.
\item[5.] Suppose $n \neq 0$ and $n$ is prime to $\character(K)$. Then $[n]$ is a separable endomorphism.
\end{enumerate}
\end{proposition}
\begin{proof}
See \cite[pages 76--77, 83, 86--87]{Silverman-Arithmetic}.
\end{proof}
Another important property that holds in general for all abelian varieties (and thus also specifically for elliptic curves) is that the number of $K$-rational points characterizes the isogeny equivalence classes.
\begin{proposition}\label{thm:IsogenyCardinality}
Let $E/K$ and $E'/K$ be two elliptic curves defined over a finite field. Then $E$ and $E'$ are isogenous over $K$ if and only if $|E(K)| = |E'(K)|$.
\end{proposition}
\begin{proof}
See \cite[pages 242--243]{Cassels-Diophantine}.
\end{proof}
\eccsection{Frobenius endomorphism}\label{sec:FrobeniusEndomorphism}
Let $E/K$ be an elliptic curve. We saw that the scalar multiplication maps $[n]$ on $E$ are endomorphisms. If we endow the set $\End_K(E)$ with an addition $+$ defined by $(\phi + \psi)(P) = \phi(P) \go \psi(P)$ for all $\phi, \psi \in \End_K(E)$, then we see that $\End_K(E)$ is in fact a ring. Thus, we have $\Z \subseteq \End_K(E)$, where the inclusion is of subrings. If the inclusion is strict, then we say that $E$ has complex multiplication. It turns out that this is always the case when the underlying field $K$ is finite, as Theorem~\ref{thm:FrobeniusEndomorphism} shows.
Before we state and prove Theorem~\ref{thm:FrobeniusEndomorphism}, we need to distinguish between two types of curves: supersingular and ordinary (or non-supersingular). Recall that the goal of the \texttt{SEA} algorithm is to determine the number of $\Fp$-rational points $|E(\Fp)|$, where $\Fp$ is prime field with a characteristic $p > 3$. We define supersingular curves over $\Fp$ to be curves for which $|E(\Fp)| = p + 1$. Clearly, this definition means that we shall mainly be concerned with ordinary curves in this paper. It is important to note that this is not the usual treatment in the literature, where supersingular curves are defined as those satisfying one of the cases in Proposition~\ref{thm:StructureOfTorsionGroup} and our definition arises as a property of those curves.
\begin{theorem}\label{thm:FrobeniusEndomorphism}
Let $E/\Fp$ be a non-supersingular curve, where $\Fp$ is a prime field of characteristic $p > 3$. Define
\begin{align*}
\phi_p: E(\cFp) &\to \{\cFp \times \cFp\} \cup \poi \\
(x, y) &\mapsto (x^p, y^p) \\
\poi &\mapsto \poi \:.
\end{align*}
Then $\phi_p$ is an endomorphism and is different from $[n]$ for all integers $n$.
\end{theorem}
\begin{proof}
Suppose $E/\Fp$ is given by the short Weierstrass equation $y^2 = x^3 + a_4x + a_6$. Then, recalling that $a_4, a_6 \in \Fp$, we have
\begin{align*}
\left(y^p\right)^2 &= \left(y^2\right)^p = \left(x^3 + a_4x + a_6\right)^p = \left(x^3\right)^p + a_4^p \left(x^p\right) + a_6^p \\
&= \left(x^p\right)^3 + a_4 \left(x^p\right) + a_6 \:.
\end{align*}
Thus, $(x^p, y^p)$ satisfies the Weierstrass equation of $E$, so $\phi_p$ is an endomorphism.
Suppose toward a contradiction that $\phi_p = [n]$ for some integer $n$. By definition of $\phi_p$, we can immediately dismiss the case $n = 0$. From Proposition~\ref{thm:BasicPropertiesOfIsogenies}(1), $\deg_s\phi_p = |\phi_p^{-1}(\poi)| = |\{\poi\}| = 1$, so $\phi_p$ is purely inseparable. It can be shown (see \cite[page 30]{Silverman-Arithmetic}) that this implies that $\deg \phi_p = p$. But then we immediately see from Proposition~\ref{thm:BasicPropertiesOfIsogenies}(4) that $\phi_p \neq [n]$ for any integer $n$, as needed.
\end{proof}
\begin{definition}\label{def:FrobeniusEndomorphism}
Let $E/\Fp$ be a non-supersingular curve. We call $\phi_p$ in Theorem~\ref{thm:FrobeniusEndomorphism} the \term{Frobenius endomorphism}.
\end{definition}
The Frobenius endomorphism is critical to the development of Schoof's algorithm, and we shall revisit it many times throughout this paper. We now turn to a closer examination of the other endomorphisms of a curve: the scalar multiplication maps.
\eccsection{Torsion points}\label{sec:TorsionPoints}
Recall the scalar multiplication maps in Definition~\ref{def:ScalarMultiplication}. We now introduce the kernel, or torsion group, of scalar multiplications in the following definition.
\begin{definition}\label{def:TorsionPoint}
Let $E/K$ be an elliptic curve and $n$ an integer. The \term{kernel of $[n]$}, denoted $E[n]$ satisfies $E[n] = \{P \in E(\overline{K}) \mid [n]P = \poi\}$. An element $P \in E[n]$ is called an \term{$n$-torsion point}.
\end{definition}
The kernels of scalar multiplications are used extensively in the development of Schoof's algorithm. The following proposition shows that these groups are of very simple forms.
\begin{proposition}\label{thm:StructureOfTorsionGroup}
Let $E/\Fp$ be an elliptic curve over a prime field of characteristic $p > 3$. Let $n$ an integer. If $p$ is prime to $n$ then
\begin{equation*}
E[n] \cong \Z/n\Z \times \Z/n\Z \:.
\end{equation*}
Otherwise, if $n = p^r$, then either
\begin{align*}
E[p^r] &= \{\poi\}, \text{ for all } r \geq 1 &&\text{or} & E[p^r] &\cong \Z/p^r\Z, \text{ for all } r \geq 1 \:.
\end{align*}
\end{proposition}
\begin{proof}
Suppose first that $p$ is prime to $n$. From Proposition~\ref{thm:BasicPropertiesOfIsogenies}, we know that $|E[n]| = |[n]^{-1}(\poi)| = \deg_s[n] = \deg[n] = n^2$. Furthermore, for any integer $d$ dividing $n$ we have $|E[d]| = d^2$. Let $n = p_1^{e_1} \cdots p_k^{e_k}$ be the prime factorization of $n$. Then on the one hand $E[p_i^{e_i}]$ does not contain any element of order greater than $p_i^{e_i}$. On the other hand, it must contain an element of order $p_i^{e_i}$ or else $|E[p_i^{c}]| > (p_i^c)^2$ for some $c < e_i$. It follows that $E[p_i^{e_i}] \cong \Z/(p_i^{e_i})\Z \times \Z/(p_i^{e_i})\Z$. It follows immediately that $E[n] \cong \Z/n\Z \times \Z/n\Z$.
Now suppose $n = p^r$. Let $\phi_p$ be the Frobenius endomorphism. Then from Proposition~\ref{thm:BasicPropertiesOfIsogenies}, and since we already showed that $\phi_p$ is purely inseparable,
\begin{align*}
|E[p^r]| &= \deg_s[p^r] = (\deg_s(\hat{\phi_p} \circ \phi_p))^r = (\deg_s\hat{\phi_p})^r \:.
\end{align*}
We also know from the same proposition and the proof of Theorem~\ref{thm:FrobeniusEndomorphism} that $\deg \hat{\phi}_p = \deg \phi_p = p$. It follows that we need to consider two cases: $\deg_s \hat{\phi}_p = 1$ and $\deg_s \hat{\phi}_p = p$. In the first case, $|E[p^r]| = 1$ for all $r$, implying that $E[p^r] = \{\poi\}$. In the second case, $|E[p^r]| = p^r$ for all $r$, which clearly means that $E[p^r] \cong \Z/p^r\Z$. This completes the proof of the proposition.
\end{proof}
The standard way of introducing supersingular curves over a prime field of characteristic $p$ is defining them to be those for which the only $p$-torsion point is the point of infinity. Since the groups of rational points for these curves have known cardinalities (\emph{i.e.}, $p + 1$), we shall focus our interest on ordinary curves, instead.
A consequence of Proposition~\ref{thm:StructureOfTorsionGroup} is the next corollary, which will be instrumental in Atkin's and Elkies' improvements to Schoof's algorithm.
\begin{corollary}\label{thm:StructureOfTorsionGroupEl}
Let $E$ be an elliptic curve over a prime field $\Fp$ of characteristic $p > 3$. Let $l < p$ a prime. Then $E[l] \cong \Fl \times \Fl$, and $E[l]$ has exactly $l+1$ cyclic subgroups $C_i$ of order $l$, where $1 \leq i \leq l+1$.
\end{corollary}
\begin{proof}
The first statement is just Proposition~\ref{thm:StructureOfTorsionGroup}, for the case $n = l < p$ a prime. Therefore, we know that $E[l]$ is generated by two points $P_1$ and $P_2$, and that $|\langle P_1 \rangle| = |\langle P_2 \rangle| = l$. For $i = 3, \ldots, l+1$ define $P_i = [i-2]P_1 \go P_2$, and note that we necessarily have $P_i \neq \poi$.
We claim that the $l+1$ cyclic subgroups $C_i$ are precisely the $\langle P_i \rangle$ we defined. First, note that $[l]P_i = [i-2][l]P_1 \go [l]P_2 = \poi$. Since $l$ is a prime, it follows that $|\langle P_i \rangle| = l$. Next, we show that $\langle P_i \rangle \neq \langle P_j \rangle$ for $i \neq j$. Clearly, this is the case if $i = 1$. Let $i,j > 1$ and suppose $P_i = [m]P_j$ for some $m$. Then,
\begin{align*}
[i-2]P_1 \go [-m][j-2]P_1 = [m-1]P_j \:,
\end{align*}
and it follows that $m=1$ and $i = j$, to prove that the groups are pairwise different. Since the groups are all of prime order, they intersect trivially, and a counting argument shows that we have all of them.
\end{proof}
\eccsection{Detour into complex analysis}\label{sec:DetourIntoComplexAnalysis}
The theory of elliptic curves is exceptionally rich over the complex field. In this section we state a few fundamental complex-analytic results. The theory relies on the observation that an elliptic curve corresponds uniquely to a lattice in the complex field (and thus, equivalently, to a torus). A moderately comprehensive development of the theory can be found in Silverman \cite{Silverman-Arithmetic}, from which we take a few important results.
Let $\Lambda = \omega_1 \Z + \omega_2 \Z$, where $\omega_1, \omega_2 \in \C$ are $\R$-linearly independent, be a lattice. We define the Weierstrass $\wp$-function corresponding to $\Lambda$.
\begin{definition}\label{def:WeierstrassPFunction}
Let $\Lambda \subset \C$ be a lattice. The Weierstrass $\wp$-function (relative to $\Lambda$) is defined by the series
\begin{equation}\label{eq:WeierstrassPFunction}
\wp(z; \Lambda) = \frac{1}{z^2} + \sum_{\omega \in \Lambda \setminus \{0\}} \frac{1}{(z - \omega)^2} - \frac{1}{\omega^2} \:.
\end{equation}
For simplicity we write $\wp(z)$ in place of $\wp(z; \Lambda)$ when the lattice has been fixed.
\end{definition}
It can be shown (see \cite[pages 153--154]{Silverman-Arithmetic}) that a Weierstrass $\wp$-function relative to $\Lambda = \omega_1 \Z + \omega_2 \Z$ is a doubly periodic function with periods $\omega_1$ and $\omega_2$, which we call the basis of $\Lambda$. Clearly, the choice of a basis in not unique (for instance, $\omega'_1 = \omega_1 + \omega_2$ and $\omega'_2 = \omega_2$ will do), and one can choose, as is conventional, $\omega_1$ and $\omega_2$ such that $\tau = \omega_1/\omega_2$ lies in the upper half-plane $\mathcal{H} = \{z \in \C \mid \Im(z) > 0\}$ of the complex plane. We call such a basis \term{homogeneous}. The following lemma states that the homogeneous bases are characterized by elements of $\SL_2(\Z)$.
\begin{lemma}\label{thm:LatticeBases}
Let $\Lambda$ be a lattice with a homogeneous basis $\Omega = \{\omega_1, \omega_2\}$. Then for any transformation $\sigma \in \SL_2(\Z)$, the action of $\sigma$ on $\Omega$ by a linear fractional transformation yields another homogeneous basis of $\Lambda$. Conversely, if $\Omega_1$ and $\Omega_2$ are two homogeneous bases of $\Lambda$ then there exists a transformation $\sigma \in \SL_2(\Z)$ such that the action of $\sigma$ on $\Omega_1$ results in $\Omega_2$.
\end{lemma}
\begin{proof}
See \cite[pages 29--30]{Lang-EllipticFunctions}.
\end{proof}
The next important theorem establishes a bijection between points on an elliptic curve over the complex field and points on the complex plain modulo a suitable lattice $\Lambda$.
\begin{theorem}\label{thm:LatticeEllipticCurve}
Let $E/\C$ be an elliptic curve given by a Weierstrass equation~\eqref{eq:Weierstrass} over the complex field. There exists a lattice $\Lambda \subset \C$ such that the map
\begin{align*}
\C/\Lambda &\to E \\
z + \Lambda &\mapsto
\begin{cases}
\left(x_\Lambda, (\wp'(z) - a_1x_\Lambda - a_3)/2\right) \:, & z \notin \Lambda \:, \\
\poi \:, & z \in \Lambda \:,
\end{cases}
\end{align*}
where $x_\Lambda = \wp(z) - b_2/12$, is a bijection. Conversely, given a lattice $\Lambda$, there exists a unique curve $E/\C$ such that the map above exists.
\end{theorem}
\begin{proof}
See \cite[page 161]{Silverman-Arithmetic}.
\end{proof}
A special case of Theorem~\ref{thm:LatticeEllipticCurve} is when $E: y^2 = x^3 + a_4x + a_6$. Then we have
\begin{equation*}
z + \Lambda \mapsto (\wp(z), \wp'(z)/2) \:, \quad z \notin \Lambda \:.
\end{equation*}
In such a case, the coefficients of the short Weierstrass equation are $a_4 = -g_2/\sqrt[3]{4}$ and $a_6 = -g_3$, where
\begin{align*}
g_2 &= 60 \sum_{\omega \in \Lambda \setminus \{0\}} \frac{1}{\omega^4} \:, &
g_3 &= 140 \sum_{\omega \in \Lambda \setminus \{0\}} \frac{1}{\omega^6} \:.
\end{align*}
Let $\Lambda \subset \C$ be a lattice with homogenous basis $\{\omega_1, \omega_2\}$ such that $\tau = \omega_1/\omega_2 \in \mathcal{H}$. Theorem~\ref{thm:LatticeEllipticCurve} associates to $\Lambda$ a curve $E/\C$, which we will denote by $E_\Lambda$. Let $q = e^{2\pi i \tau} \in \C$ and define $j(q)$ to be the $j$-invariant of $E_\Lambda$. Recall that $j$-invariants classify isomorphism classes over $\C$ (we showed this in Proposition~\ref{thm:AbsoluteInvariantIsomorphism} for the closure of a finite field $\overline{K}$, but the result holds in general). Note that if $\Lambda' \subset \C$ is a lattice with the homogenous basis $\{c\omega_1, c\omega_2\}$ for some nonzero $c \in \C$, then $(c\omega_1)/(c\omega_2) = \omega_1/\omega_2 = \tau$. Therefore, we would expect the elliptic curves corresponding to $\Lambda$ and $\Lambda'$ to be isomorphic. The following proposition ensures that this is indeed the case. It also plays a role in the \texttt{SEA} algorithm when we discuss how to construct a special polynomial from a kernel of an isogeny.
\begin{proposition}\label{thm:IsomorphicLattices}
Let $\Lambda, \Lambda' \subset \C$ be two lattices. The elliptic curves corresponding to $\Lambda$ and $\Lambda'$ are isomorphic if and only if $\Lambda = c\Lambda'$ for some nonzero $c \in \C$.
\end{proposition}
\begin{proof}
See \cite[page 161]{Silverman-Arithmetic}.
\end{proof}
For any $\tau \in \mathcal{H}$, we define the following lattice: $\Lambda_\tau = \Z + \tau\Z$. A direct consequence of Proposition~\ref{thm:IsomorphicLattices} is that for any lattice $\Lambda \subset \C$ we can find a nonzero $c \in \C$ such that $c\Lambda = \Lambda_\tau$ for some $\tau \in \mathcal{H}$. In Proposition~\ref{thm:IsomorphicLatticesFundamental} we will improve this result even further, but first we would like to motivate the discussion by recalling the $j$-invariants of curves.
In the discussion above, we defined $j(q)$ indirectly, in terms of the corresponding elliptic curve $E$. It turns out we can define $j(q)$ directly in terms of $q$. Such a procedure would be well-defined only if we can show that $j(q)$ is independent of the choice of $\tau = \omega_1/\omega_2$. From Lemma~\ref{thm:LatticeBases} we know that it suffices to show that for all $\sigma \in \SL_2(\Z)$, we have $j(q) = j(q_\sigma)$ where $q_\sigma = e^{2\pi i \sigma\{\omega_1, \omega_2\}}$. The proposition below uses this fact to show that we can pick $\tau$ in the standard fundamental region $\mathcal{F} = \{\tau \in \C \mid \Im(\tau) > 0, -1/2 \leq \Re(\tau) < 1/2, |\tau| \geq 1\}$.
\begin{proposition}\label{thm:IsomorphicLatticesFundamental}
Let $\Lambda \subset \C$ be a lattice. Then there exists a nonzero $c \in \C$ such that $c\Lambda = \Lambda_\tau$ for some $\tau \in \mathcal{F}$.
\end{proposition}
\begin{proof}
See \cite[page 343]{Silverman-Arithmetic}.
\end{proof}
We now show how to define $j(q)$ directly. To that end, let $\Z\llbracket q\rrbracket$ be the ring of formal power series over the integers in the variable $q$. Define in $\Z\llbracket q\rrbracket$ the following series:
\begin{align*}
E_2(q) &= 1 - 24\sum_{n=1}^\infty \frac{nq^n}{1-q^n} \:, &
E_4(q) &= 1 + 240\sum_{n=1}^\infty \frac{n^3q^n}{1-q^n} \:, \\
E_6(q) &= 1 - 504\sum_{n=1}^\infty \frac{n^5q^n}{1-q^n} \:.
\end{align*}
We define two more formal power series, this time in $\Z[\zeta, \frac{1}{\zeta(1-\zeta)}]\llbracket q\rrbracket$:
\begin{align*}
x(\zeta; q) &= \frac{1}{12} - 2\sum_{n=1}^\infty \frac{q^n}{(1-q^n)^2} + \sum_{n \in \Z} \frac{\zeta q^n}{(1-\zeta q^n)^2} \:, \\
y(\zeta; q) &= \frac{1}{2} \sum_{n \in \Z} \frac{\zeta q^n (1 + \zeta q^n)}{(1 - \zeta q^n)^3} \:.
\end{align*}
Then with the above power series, the following proposition can be established:
\begin{proposition}\label{thm:EllipticSeries}
The following equalities of power series hold:
\begin{align}\label{eq:EllipticSeries}
y^2 &= x^3 - \frac{E_4(q)}{48}x + \frac{E_6(q)}{864} \:, \\
p_1 &= \!\!\sum_{\zeta \in \mu_l, \zeta \neq 1}\!\! x(\zeta; q) = \frac{1}{12}l \left( E_2(q) - lE_2(q^l)\right) \:, \label{eq:FirstCoefficient}
\end{align}
where $x = x(\zeta; q)$, $y = y(\zeta; q)$, and $\mu_l$ is the set of complex $l$-th roots of unity.
\end{proposition}
\begin{proof}
See \cite[page 245]{Schoof-Counting}.
\end{proof}
Schoof (in \cite{Schoof-Counting} and further examined by others in \cite{Blake-Elliptic}) notes that $E_4(q)$ and $E_6(q)$ are integers in some number field $K$, with a ring of integers $\mathcal{O}_K$. Furthermore, $\mathcal{O}_K$ contains a prime ideal $\BB$ with residue field $\Fp$ such that $E_4(q)$ and $E_6(q)$ modulo $\BB$ are elements of $\Fp$.
Let $E/\C$ be an elliptic curve with a $j$-invariant $j_E \notin \{0,1728\}$. In Equation~\eqref{eq:ShortWeierstrass} we introduced the short Weierstrass equation of an elliptic curve over a field of prime characteristic greater than 3. Later, in Equation~\eqref{eq:ShortJInvariant}, we derived the $j$-invariant of such a curve. Both of these results also hold for fields of characteristic zero, such as the complex field. Thus, we can assume $E$ is given by the short Weierstrass equation~\eqref{eq:ShortWeierstrass}. Equation~\eqref{eq:EllipticSeries} establishes that
\begin{align}\label{eq:EllipticSeriesCoefficients}
E_4(q) &\equiv - 48a_4 \pmod{\BB} &&\text{and}& E_6(q) &\equiv 864a_6 \pmod{\BB}
\end{align}
Thus, if we substitute the value $q$ associated with an elliptic curve $E$ into the formal series
\begin{equation}\label{eq:JSeries}
j(q) = 1728 \left(\frac{E_4(q)^3}{E_4(q)^3 - E_6(q)^2}\right) = \frac{1}{q} + 744 + 196884q + 21493760q^2 + \cdots \:,
\end{equation}
then the resultant value is the $j$-invariant $j_E$.
\eccsection{Division polynomials}\label{sec:DivisionPolynomials}
Through the remainder of this section, let $p$ a prime greater than 3.
Consider an elliptic curve $E/\Fp$ over a prime field of characteristic $p$. We wish to associate to this curve a set of multivariate polynomials and a related set of univariate polynomials, both called division polynomials. These polynomials arise from the complex analytic structure that we explored in the previous section. We present two important results in this section. The first is that the nontrivial torsion points are precisely the roots of corresponding division polynomials, as we shall see in Theorem~\ref{thm:DivisionPolynomialsAndTorsionGroup}. The second result we discuss in this section is Theorem~\ref{thm:DivisionPolynomials}, where we find that the division polynomials are intimately related to the scalar multiplications endomorphisms. Both of these results will be used in Schoof's algorithm.
\begin{definition}\label{def:DivisionPolynomials}
Let $E/\Fp$ be an elliptic curve given by a short Weierstrass equation~\eqref{eq:ShortWeierstrass}. Define recursively the \term{$m$-th division polynomial} $\psi_m \in \Fp[x,y]$ as
\begin{equation*}
\begin{aligned}
\psi_0 &= 0 \:, \\
\psi_1 &= 1 \:, \\
\psi_2 &= 2y \:, \\
\psi_3 &= 3x^4 + 6a_4x^2 + 12a_6x - a_4^2 \:, \\
\psi_4 &= 4y\left(x^6 + 5a_4x^4 + 20a_6x^3 - 5a_4^2x^2 - 4a_4a_6x - 8a_6^2 - a_4^3\right) \:, \\
\psi_{2m+1} &= \psi_{m+2}\psi_m^3 - \psi_{m-1}\psi_{m+1}^3 \:, \quad m \geq 2 \:, \\
\psi_{2m} &= \frac{\left(\psi_{m+2}\psi_{m-1}^2 - \psi_{m-2}\psi_{m+1}^2\right)\psi_m}{2y}\:, \quad m > 2 \:.
\end{aligned}
\end{equation*}
where for simplicity we suppress the arguments of $\psi_m$.
\end{definition}
First, we claim that the numerator of $\psi_{2m}$, where $m > 2$, is divisible by $4y^2$. Thus, in particular the numerator is divisible by the denominator $2y$, so the definition of $\psi_{2m}$ makes sense. We have
\begin{align*}
\psi_6 &= \frac{(\psi_5\psi_2^2 - \psi_1\psi_4^2)\psi_3}{4y^2} \\
&= \frac{4y^2\left(\psi_5 - 4\left(x^6 + 5a_4x^4 + 20a_6x^3 - 5a_4^2x^2 - 4a_4a_6x - 8a_6^2 - a_4^3\right)^2\right)\psi_3}{4y^2} \:,
\end{align*}
so the claim holds in this case. If $m$ is even, then so are $m+2$ and $m-2$. Otherwise, $m$ is odd, so both $m-1$ and $m+1$ are even. It follows by induction that regardless of whether $m$ is even or odd, the numerator of $\psi_{2m}$ is divisible by $4y^2$, and the claim follows.
The evaluation of $\psi_m$ is always taken at points on the curve. Therefore, we may write the division polynomials modulo the Weierstrass equation of the elliptic curve. In particular, it follows that the degree of $\psi_m$ in $y$ is never greater than one. Furthermore, we already know that $\psi_{2m}$ is divisible by $2y$. This observation gives rise to the first statement in the following important theorem, which ties the $m$-th division polynomial with the subgroup of $m$-torsion points $E[m]$.
\begin{theorem}\label{thm:DivisionPolynomialsAndTorsionGroup}
Let $m$ be a nonnegative integer. Define a polynomial $f_m$ in the polynomial ring $\Fp[x,y]$ as follows:
\begin{equation*}
f_m(x,y) =
\begin{cases}
\psi_m(x,y) & m \text{ odd,} \\
\psi_m(x,y)/2y & m \text{ even.}
\end{cases}
\end{equation*}
\begin{enumerate}
\item $f_m$ depends only on $x$.
\item The degree of $f_m$ in $x$ is at most $(m^2 - 1)/2$ if $m$ is odd, and at most $(m^2 - 4)/2$ if $m$ is even. The degrees are exact if $p$ does not divide $m$ for an odd $m$, or $m/2$ for an even $m$.
\item Let $P \neq \poi$ be a point on the elliptic curve $E/\Fp$ such that $[2]P \neq \poi$, and let $m \geq 1$. Then $P = (x,y) \in E[m]$ if and only if $f_m(x) = 0$.
\item If $m$ is an odd prime not equal to $p$, then $f_m$ has no other root in any extension of $\Fl$.
\end{enumerate}
\end{theorem}
\begin{proof}
We already know that $\psi_{2m}$ is divisible by $2y$, so that the definition of $f_m$ makes sense. We now prove that $f_m$ depends only on $x$ by induction. This clearly holds for $0 \leq m \leq 4$. We have $f_{2k+1} = \psi_{2k+1} = \psi_{k+2}\psi_k^3 - \psi_{k-1}\psi_{k+1}^3$. It follows that
\begin{equation*}
f_{2k+1} =
\begin{cases}
f_{k+2}f_k^3 - 16 (x^3 + a_4x + a_6)^2 f_{k-1}f_{k+1}^3 & k \text{ is odd,} \\
16 (x^3 + a_4x + a_6)^2 f_{k+2}f_k^3 - f_{k-1}f_{k+1}^3 & k \text{ is even.}
\end{cases}
\end{equation*}
In addition,
\begin{equation*}
f_{2k} = \frac{\psi_{2k}}{2y} = \frac{(\psi_{k+2}\psi_{k-1}^2 - \psi_{k-2}\psi_{k+1}^2)\psi_k}{4y^2} = (f_{k+2}f_{k-1}^2 - f_{k-2}f_{k+1}^2)f_k \:,
\end{equation*}
regardless of whether $k$ is odd or even. By induction, $f_m$ depends only on $x$, to prove the first statement. By abuse of notation, we will consider $f_m$ as a univariate polynomial in the ring $\Fp[x]$.
The second and third statements follow from the way the division polynomials are introduced in the context of a complex plane modulo a suitable lattice. See Lang \cite[pages 33--34]{Lang-EllipticCurves} for more details.
If $m$ a prime not equal to $p$, then by Proposition~\ref{thm:StructureOfTorsionGroup} there are $m^2 - 1$ nontrivial $m$-torsion points. If we further assume that $m$ is odd, then there are $(m^2 - 1)/2$ different $x$-coordinates of the nontrivial $m$-torsion points. Furthermore, from the second statement, the degree of $f_m$ is also $(m^2 - 1)/2$. The last statement of the theorem follows immediately.
\end{proof}
We now proceed to proving the second important result of this section. We show that the scalar multiplication endomorphisms can be expressed in terms of the division polynomials.
\begin{theorem}\label{thm:DivisionPolynomials}
Let $E/\Fp$ be an elliptic curve. Let $m$ be a positive integer and $P = (x,y) \in E(\cFp)$ a point with $[m]P \neq \poi$. Then
\begin{equation}\label{eq:ScalarMultiplicationWithDivisionPolynomials}
[m]P = \left(x - \frac{\psi_{m-1}\psi_{m+1}}{\psi_m^2}, \frac{\psi_{m+2}\psi_{m-1}^2 - \psi_{m-2}\psi_{m+1}^2}{4y\psi_m^3} \right) \:.
\end{equation}
\end{theorem}
\begin{proof}
We assume the curve is given by the short Weierstrass equation~\eqref{eq:ShortWeierstrass}. There are two observations to be made here. The first is that under the equivalence we showed in Section~\ref{sec:DetourIntoComplexAnalysis} between curves and lattices in the complex plain, if $z \in \C \setminus \Lambda$ corresponds to a point $(\wp(z), \wp'(z)/2)$ on the curve of order not dividing $m$, then $mz$ corresponds to a point $[m](\wp(z), \wp'(z)/2) = (\wp(mz), \wp'(mz)/2)$. This result holds whenever $E$ is considered over a field of characteristic not equal to 2 or 3. With some squinting, this result seems plausible, and we refer the reader to Lang's \cite{Lang-EllipticCurves} treatment for the necessary details.
The second observation, proven in \cite[pages 34--36]{Lang-EllipticCurves}, is that for $u, v \in \C$ with $u-v \not\equiv 0 \pmod{\Lambda}$ we have
\begin{align*}
\wp(mz) &= \wp(z) - \frac{\psi_{m-1}\psi_{m+1}}{\psi_m^2} & &\text{and}&
\wp(u + v) - \wp(u - v) &= -\frac{\wp'(u)\wp'(v)}{(\wp(u) - \wp(v))^2} \:.
\end{align*}
Substituting $u = mz$ and $v = z$ (which is legal when $P$ is not an $m$-torsion point) and rearranging, we find
\begin{align*}
\wp(z)\wp'(mz) &= -\Bigl(\wp\bigl((m+1)z\bigr) - \wp\bigl((m-1)z\bigr)\Bigr)\bigl(\wp(mz) - \wp(z)\bigr)^2 \\
&= \left(\frac{\psi_{m}\psi_{m+2}}{\psi_{m+1}^2} - \frac{\psi_{m-2}\psi_{m}}{\psi_{m-1}^2}\right)\left(\frac{\psi_{m-1}\psi_{m+1}}{\psi_m^2}\right)^2 \\
&= \frac{\psi_{m+2}\psi_{m-1}^2 - \psi_{m-2}\psi_{m+1}^2}{\psi_m^3} \:.
\end{align*}
From here the proof is immediate. If $P = (x,y) = (\wp(z), \wp'(z)/2)$ is a point such that $[m]P \neq \poi$, then
\begin{equation*}
[m]P = (\wp(mz), \wp'(mz)/2) = \left(x - \frac{\psi_{m-1}\psi_{m+1}}{\psi_m^2}, \frac{\psi_{m+2}\psi_{m-1}^2 - \psi_{m-2}\psi_{m+1}^2}{4y\psi_m^3}\right)\:,
\end{equation*}
as needed.
\end{proof}
\eccsection{Modular polynomials}\label{sec:ModularPolynomials}
We conclude our survey of the arithmetic of elliptic curves by introducing the modular polynomials. These polynomials will be used extensively in our description of the Elkies and Atkin procedures.
Recall from the Section~\ref{sec:DetourIntoComplexAnalysis} that we can associate to each elliptic curve $E/\C$ an invariant $\tau \in \mathcal{F}$, unique up to isomorphism of curves. We also defined $q = e^{2\pi i \tau} \in \C$ and found that we can express the $j$-invariant of $E$ in terms of a formal series $j(q)$. For simplicity, we change notation in this section from the previous one and define $j(\tau) = j_E$.
For any positive integer $n$, define
\begin{equation*}
S_n^* = \left\{\begin{pmatrix} a & b \\ 0 & d \end{pmatrix} \right|
\left. a,b,d \in \Z, 0 \leq b < d, ad = n, \gcd(a,b,d) = 1
\vphantom{\begin{pmatrix} a & b \\ 0 & d \end{pmatrix}} \right\} \:.
\end{equation*}
For $\alpha = \left(\begin{smallmatrix} a & b \\ 0 & d \end{smallmatrix}\right) \in S_n^*$, we define the map
\begin{equation*}
j \circ \alpha(\tau) = j\left(\frac{a\tau + b}{d}\right) \:.
\end{equation*}
Then, we can define the modular polynomials as follows:
\begin{definition}\label{def:ModularPolynomials}
Let $n$ be a positive integer. Then the \term{$n$-th modular polynomial} is given by the equation
\begin{equation*}
\Phi_n(x,j) = \prod_{\alpha \in S_n^*} (x - j \circ \alpha) \:.
\end{equation*}
\end{definition}
The following lemma derives the relation between modular polynomials and isogenous elliptic curves over $\C$.
\begin{lemma}\label{thm:ZerosOfModularPolynomialComplex}
Let $E_1/\C$ and $E_2/\C$ be two elliptic curves with $j$-invariants $j_{E_1}$ and $j_{E_2}$, respectively. Then $\Phi_n(j_{E_1}, j_{E_2}) = 0$ if and only if there is an isogeny from $E_1$ to $E_2$ whose kernel is cyclic of degree $n$.
\end{lemma}
\begin{proof}
This is adopted from an exercise in \cite[page 182]{Silverman-Advanced}.
\end{proof}
The next theorem establishes an analogous statement for curves over finite fields. Its result is instrumental in Atkin's classification of primes. We shall also encounter this theorem in the context of constructing factors of divisional polynomials.
\begin{theorem}\label{thm:ZerosOfModularPolynomial}
Let $l$ be a prime, $\Fp$ be a finite field with $p \neq l$, and $E$ an elliptic curve over $\Fp$. Then the $l+1$ zeros $\tj \in \cFp$ of the polynomial $\Phi_l(x, j(E)) = 0$ are precisely the $j$-invariants of the isogenous curves $\tilde{E} = E/C$ with $C$ one of the $l+1$ cyclic subgroups of $E[l]$.
\end{theorem}
\begin{proof}
See \cite[pages 44--46]{Muller-Algorithmus}.
\end{proof}
As has become customary with introductory texts to elliptic curve cryptography, we provide the modular polynomials for $l = 3$ and $l = 5$. The following are taken from \cite{Blake-Elliptic} and the excellent \textsc{sage} code \cite{Stein-Module}.
\begin{align*}
\Phi_3(x,y) &= x^4 - x^3y^3 + y^4 \\
& \quad + 2232 (x^3y^2 + x^2y^3) \\
& \quad - 1069956 (x^3y + xy^3) \\
& \quad + 36864000 (x^3 + y^3) \\
& \quad + 2587918086 x^2y^2 \\
& \quad + 8900222976000 (x^2y + xy^2) \\
& \quad + 452984832000000 (x^2 + y^2) \\
& \quad - 770845966336000000 xy \\
& \quad + 1855425871872000000000 (x + y) \:,
\end{align*}
and
\begin{align*}
\Phi_5(x,y) &= x^6 - x^5y^5 + y^6 \\
& \quad + 3720 (x^5y^4 + x^4y^5) \\
& \quad - 4550940 (x^5y^3 + x^3y^5) \\
& \quad + 2028551200 (x^5y^2 + x^2y^5) \\
& \quad - 246683410950 (x^5y + xy^5) \\
& \quad + 1963211489280 (x^5 + y^5) \\
& \quad + 1665999364600 x^4y^4 \\
& \quad + 107878928185336800 (x^4y^3 + x^3y^4) \\
& \quad + 383083609779811215375 (x^4y^2 + x^2y^4) \\
& \quad + 128541798906828816384000 (x^4y + xy^4) \\
& \quad + 1284733132841424456253440 (x^4 + y^4) \\
& \quad - 441206965512914835246100 x^3y^3 \\
& \quad + 26898488858380731577417728000 (x^3y^2 + x^2y^3) \\
& \quad - 192457934618928299655108231168000 (x^3y + xy^3) \\
& \quad + 280244777828439527804321565297868800 (x^3 + y^3) \\
& \quad + 5110941777552418083110765199360000 x^2y^2 \\
& \quad + 36554736583949629295706472332656640000 (x^2y + xy^2) \\
& \quad + 6692500042627997708487149415015068467200 (x^2 + y^2) \\
& \quad - 264073457076620596259715790247978782949376 xy \\
& \quad + 53274330803424425450420160273356509151232000 (x + y) \\
& \quad + 141359947154721358697753474691071362751004672000 \:.
\end{align*}
As is evident from these examples, the coefficient of the modular polynomials increase rapidly. Luckily, there exist other polynomials that satisfy similar properties as in Theorem~\ref{thm:ZerosOfModularPolynomial}. We will allude to this fact when we discuss the \texttt{SEA} algorithm.
%=======================================================
\eccpart{\texttt{SEA} Algorithm}\label{sec:SEAAlgorithm}
%=======================================================
Throughout this section we assume that $E$ is an elliptic curve of a prime field $\Fp$ of characteristic $p > 3$.
In Section~\ref{sec:SecurityOfECC} we showed that the security of an elliptic curve cryptosystem depends on the order of the group of rational points $E(\Fp)$. Therefore, it is of great interest to be able to determine the order of $E(\Fp)$ in an efficient manner. As discussed in \cite{Blake-Elliptic}, there are methods of constructing elliptic curves $E/\Fp$ for which the order of the group $E(\Fp)$ is easily determined. However, these methods impose additional structure on the curve. Thus, non-generic algorithms may leverage this additional structure in solving the DLP in this curves.
The Schoof-Elkies-Atkin (\texttt{SEA}) algorithm, however, does not assume any structural properties of the underlying elliptic curve, as long as it is an ordinary curve. Coupled with its efficient implementation over fields of large prime characteristic, the algorithm is the preferred method of determining the order of the group of rational points of an arbitrary elliptic curve \cite{Cohen-Handbook17}.
In the following sections, we first present an important result by Hasse (which was later generalized by Weil) tying the order of $E(\Fp)$ to the one of $\Fp$. Next, we explain in some detail the original Schoof algorithm, in which we consider the trace of the Frobenius endomorphism (to be explained later) modulo different primes. This algorithm, while of polynomial complexity in the logarithm of the field characteristic, is still very slow in practice. We then turn our attention to Atkin's and Elkies' improvements to the algorithm, which resulted in a very practical running time. The first result, due to Atkin, is the classification of different primes into two groups: Atkin primes and Elkies primes. In the case of Atkin primes, further analysis of the Frobenius endomorphism as an element of $\PGL(\Fl)$ would prove useful. In the case of Elkies primes, we will be able to invoke complex analytic results to help us compute the group order.
\eccsection{Schoof's algorithm}\label{sec:SchoofsAlgorithm}
Consider an elliptic curve $E$ over $\Fp$. The following theorem, proven by Hasse, states that the number of $\Fp$-rational points of $E$ is roughly equal to the number of elements in the field $\Fp$ plus one. There is an intuitive reasoning explaining this result: each of the $p$ possible values of $x$ gives rise to two values of $y$ if $x^3 + a_4x + a_6$ is a square, and no value of $y$ if it is not a square. Assuming that the distribution of the possible $x^3 + a_4x + a_6$ values is nearly ``uniform,'' we would expect half of these values to be squares. We add to this number the point of infinity, which is by definition rational, to arrive at the expected number of $p+1$ rational points.
\begin{theorem}[Hasse]\label{thm:Hasse}
Let $E$ be an elliptic curve defined over $\Fp$. Then
\begin{equation}\label{eq:Hasse}
|E(\Fp)| = p + 1 - t \:,
\end{equation}
where $|t| \leq 2\sqrt{p}$.
\end{theorem}
\begin{proof}
See \cite[page 131]{Silverman-Arithmetic}.
\end{proof}
The error term $t$ is intimately related to the Frobenius endomorphism described in Theorem~\ref{thm:FrobeniusEndomorphism}. The missing link is the characteristic polynomial which we define next.
\begin{definition}\label{def:FrobeniusCharacteristicAndTrace}
Let $\phi_p$ be the Frobenius endomorphism as in Theorem~\ref{thm:FrobeniusEndomorphism}. We call the polynomial
\begin{equation*}
\chi(T) = T^2 + tT + p
\end{equation*}
the \term{characteristic polynomial of the Frobenius endomorphism}, where $t$ is the error term, also called the \term{trace of the Frobenius endomorphism}, as in Theorem~\ref{thm:Hasse}.
\end{definition}
The relation between the Frobenius endomorphism and Hasse's Theorem is thus realized in the following theorem.
\begin{theorem}\label{thm:CharacteristicPolynomial}
The Frobenius endomorphism $\phi_p$ satisfies
\begin{equation}\label{eq:CharacteristicPolynomial}
\chi(\phi_p) = \phi_p^2 - [t]\phi_p + [p] = [0] \:,
\end{equation}
where $t$ is the trace of the Frobenius endomorphism and $[n]$ is the scalar multiplication by $n$.
\end{theorem}
\begin{proof}
See \cite[pages 135--136]{Silverman-Arithmetic}.
\end{proof}
Hasse's theorem assures us that the trace of the Frobenius endomorphism $t$ satisfies $|t| \leq 2\sqrt{p}$. Furthermore, it asserts that if we can find $t$ then we can determine the number of $\Fp$-rational points of $E/\Fp$. Therefore, it suffices to find $t$ modulo some integer greater than $4\sqrt{p}$. Schoof's approach to the problem of finding the trace $t$ was to determine $t$ modulo primes $l_1, \ldots, l_r$ satisfying $\prod_{i=1}^r l_i > 4\sqrt{p}$. Then, using the Chinese remainder theorem, one could easily find $t$.
To determine $t$ modulo a small prime $l$, we first consider the case $l = 2$. Since $p$ is an odd prime, we know from Hasse's theorem that $|E(\Fp)| = p + 1 - t \equiv t \pmod{2}$. Clearly, $\poi \in E(\Fp)$, and if $P = (x,y) \in E(\Fp)$ then $-P = (x,-y) \in E(\Fp)$. Thus, if $E$ has no nontrivial points of order 2, then we have found that $t \equiv 1 \pmod{2}$. Otherwise, $E$ may have either one or three points of order 2, in which case $t \equiv 0 \pmod{2}$.
Note that determining that a curve $E: y^2 = x^3 + a_4x + a_6$ has a nontrivial point of order 2 is equivalent to determining that $x^3 + a_4x + a_6$ is reducible in $\Fp$, which is in turn equivalent to finding nontrivial factor of $x^3 + a_4x + a_6$ and $x^p - x$.
Now consider the case $l$ is an odd prime. Recall from Theorem~\ref{thm:CharacteristicPolynomial} that the Frobenius endomorphism $\phi_p$ satisfies Equation~\eqref{eq:CharacteristicPolynomial}. We restrict the characteristic polynomial of $\phi_p$ to the group of $l$-torsion points $E[l]$ to yield the equation
\begin{equation*}\label{eq:RestrictedCharacteristicPolynomial}
\phi_p^2 - [t_l]\phi_p + [p_l] = [0]
\end{equation*}
in $\End(E)$, where $t_l \equiv t \pmod{l}$, $p_l \equiv p \pmod{l}$ and $0 \leq t_l, q_l < l$. Thus, the problem of finding $t_l$ amounts to finding an integer $0 \leq \tau < l$ such that
\begin{equation}\label{eq:TauCharacteristicPolynomial}
\phi_p^2(P) \go [p_l]P = [\tau]\phi_p(P)
\end{equation}
for all nontrivial $l$-torsion points $P \in E[l] \setminus \{\poi\}$. Note that $\tau$ is unique: if $\tau_1$ and $\tau_2$, with $0 \leq \tau_1, \tau_2 < l$, both satisfy~\eqref{eq:TauCharacteristicPolynomial}, then we have $[\tau_1]\phi_p(P) = [\tau_2]\phi_p(P)$. Equivalently, $[\tau_d]\phi_p(P) = [0]$, where $\tau_d = |\tau_1 - \tau_2|$ for all nontrivial $l$-torsion points $P$. Since $P \neq \poi$, also $\phi_p(P) \neq \poi$ and it follows that $\tau_d \mid l$. But then, since $l$ is a prime and $0 \leq \tau_1, \tau_2 < l$, we must have $\tau_1 = \tau_2$, to establish uniqueness.
The heart of Schoof's algorithm lies in the fact that we need not compute the coordinates of the points $\phi_p^2(P) = (x^{p^2}, y^{p^2})$ and $\phi_p(P) = (x^p, y^p)$. Computing these coordinates would indeed be very expensive. However, in Theorem~\ref{thm:DivisionPolynomialsAndTorsionGroup} we showed that the nontrivial $l$-torsion points are precisely the roots of the $l$-th division polynomial $f_l$. Furthermore, to compute $[p_l](x,y)$ and $[\tau](x^p, y^p)$ we may also use the polynomials $f_l$, as shown in Theorem~\ref{thm:DivisionPolynomials}. Thus, our computations can be carried out in the polynomial ring $\Fp[x,y]/(f_l(x), E(x,y))$, where $E(x,y) = y^2 - x^3 - a_4x - a_6$ is the short Weierstrass equation~\eqref{eq:ShortWeierstrass}.
We explain the algorithm in more detail, following the original introduction of the algorithm by Schoof in \cite{Schoof-Elliptic} and further discussion by Blake, Seroussi, and Smart in \cite{Blake-Elliptic}. Let $l$ be an odd prime, and let $P = (x,y)$ be a nontrivial $l$-torsion point, where we treat the coordinates as indeterminate. Our first main goal is to compute and compare the $x$-coordinates of $(x^{p^2}, y^{p^2}) \go [p_l](x,y)$ and $[\tau](x^p, y^p)$ for $0 \leq \tau < l$. In fact, since the $x$-coordinates of $[\tau](x^p, y^p)$ and its inverse $[l-\tau](x^p, y^p)$ are identical, it suffices to check $0 \leq \tau \leq (l-1)/2$.
We distinguish between two cases. In the first case, $\phi_p^2(Q) \neq \pm[p_l]Q$ for all nontrivial $l$-torsion points $Q$. In particular, this means that $t_l \neq 0$, and that $\phi_p^2(Q)$ and $\pm[p_l]Q$ have different $x$-coordinates. In the second case, there exists a nontrivial $l$-torsion point $P = (x,y)$ for which $\phi_p^2(P) = [p_l]P$ or $\phi_p^2(P) = -[p_l]P$. Note that in this case the $x$-coordinates of $\phi_p^2(P)$ and $\pm[p_l]P$ are the same. That is, we have
\begin{align*}
x^{p^2} = x - \frac{\psi_{p_l - 1}\psi_{p_l + 1}}{\psi_{p_l}^2} \:.
\end{align*}
Using the results of Theorem~\ref{thm:DivisionPolynomialsAndTorsionGroup}, we see that such a point $P$ exists if and only if we have $\gcd(\psi_{p_l}^2(x^{p^2} - x) + \psi_{p_l - 1}\psi_{p_l + 1}, \psi_l) \neq 1$, so there is a simple test to separate the cases. In practice, we shall transform the expressions above and compute the greatest common divisor with the univariate division polynomials $f_i$.
\emph{Case 1:} Here, $\phi_p^2(Q) \neq \pm[p_l]Q$ for all nontrivial $l$-torsion points $Q$. Using Equations~\eqref{eq:ShortGroupLaw} and~\eqref{eq:ScalarMultiplicationWithDivisionPolynomials}, we have
\begin{align*}
\bigl(x^{p^2}, y^{p^2}\bigr) &\go [p_l](x,y) \\
&= \left(\lambda^2 - x^{p^2} - x + \frac{\psi_{p_l - 1}\psi_{p_l + 1}}{\psi_{p_l}^2} , \lambda\Bigl(2x^{p^2} - \lambda^2 + x - \frac{\psi_{p_l - 1}\psi_{p_l + 1}}{\psi_{p_l}^2}\Bigr) - y^{p^2}\right) \:,
\end{align*}
where
\begin{align*}
\lambda = \frac{4y^{p^2+1}\psi_{p_l}^3 - \psi_{p_l + 2}\psi_{p_l - 1}^2 + \psi_{p_l - 2}\psi_{p_l + 1}^2}{4y\psi_{p_l}\left(\psi_{p_l}^2(x^{p^2} - x) + \psi_{p_l - 1}\psi_{p_l + 1}\right)} \:.
\end{align*}
If $p_l = 1$, then $\psi_{p_l - 2}$ is not defined. However, in this case we need to compute $(x^{p^2}, y^{p^2}) \go (x,y)$, which is easy.
Thus, after finding a common denominator, we can write the $x$-coordinate of $(x^{p^2}, y^{p^2}) \go [p_l](x,y)$ as $h_1/h_2$ for some $h_1, h_2 \in \Fl[x,y]$. The $x$-coordinate of $[\tau](x,y)$ is written similarly as $h_3/h_4$ for some $h_3, h_4 \in \Fl[x,y]$. We will be computing $[\tau](x,y)$ for potentially many values of $\tau$, so it may be preferred to write this expression leaving $\tau$ indeterminate.
Of course, the whole point of the algorithm is that we can make the computations considerably easier by reducing modulo the curve equation and the division polynomial $f_l$. Thus, we can and will reduce all powers of $y$ greater than one and all powers of $x$ greater than the degree of $f_l$, which is of the order $O(l^2)$. We equate the two resultant expressions, and by clearing denominators we obtain an expression of the form $a(x) - yb(x) = 0$ for $a, b \in \Fl[x]$. Substituting into the curve equation yields an expression $h_X(x) = 0$ for $h_X \in \Fl[x]$.
We need to determine if there exists one (and thus all) nontrivial $l$-torsion point $P = (x,y)$ for which $h_X(x) = 0$. As indicated in Theorem~\ref{thm:DivisionPolynomialsAndTorsionGroup}, a necessary and sufficient condition for the existence of such a point is that $x$ is a root of $f_l$. Hence, if $\gcd(h_X, f_l) = 1$ then such a point does not exist and another value of $\tau$ should be tried. Otherwise, a nontrivial $l$-torsion point $P$ satisfying Equation~\eqref{eq:TauCharacteristicPolynomial} exists for either $\tau$ or $l-\tau$, and it remains to find which of the two holds. This can be done by similarly computing and comparing the $y$-coordinates of $(x^{p^2}, y^{p^2}) \go [p_l](x,y)$ and $[\tau](x^p, y^p)$. If the two are equal, then we take $t_l = \tau$. Otherwise, we take $t_l = l-\tau$. Note that if in the computation of $[\tau](x,y)$ we have not left $\tau$ as indeterminate, then we in fact have $h_X \equiv 0 \pmod{f_l}$ whenever nontrivial $l$-torsion points satisfy Equation~\eqref{eq:TauCharacteristicPolynomial} with $t_l = \pm \tau$.
\emph{Case 2:}\label{page:SchoofCaseTwo} Here, there exists a nontrivial $l$-torsion point $P$ for which $\phi_p^2(P) = \pm[p_l]P$. Note that if $\phi_p^2(P) =[p_l]P$ then we must have $[2p_l]P = [t_l]\phi_p(P)$. Equivalently, $\phi_p(P) = [\frac{2p_l}{t_l}]P$. We apply the Frobenius endomorphism on both sides to find
\begin{align*}
[p_l]P &= \phi_p^2(P) = \phi_p\left(\Bigl[{\frac{2p_l}{t_l}}\Bigr]P\right) = \Bigl[{\frac{4p_l^2}{t_l^2}}\Bigr]P \:.
\end{align*}
Therefore, in this case $t^2 \equiv 4p_l \pmod{l}$ and thus $p_l$ is a square in $\Fl$, say with $p_l \equiv \omega^2 \pmod{l}$ for some $\omega \in \Fl$. Note that in this case either $\omega$ or $-\omega$ is an eigenvalue of the Frobenius endomorphism: $\phi_p(P) = [\omega]P$ or $\phi_p(P) = [-\omega]P$.
This suggests the following treatment of Case 2. First we check if $\left(\frac{p_l}{l}\right) = -1$. If this is the case, then $\phi_p^2(P) = -[p_l]P$ and we conclude that $t_l = 0$. Otherwise, we can find a square root $\omega$ of $p_l$ in $\Fl$. Next we check whether $\omega$ or $-\omega$ is an eigenvalue of the Frobenius endomorphism. This test is similar to the test which separated Case~1 and Case~2 above: if $\gcd(\psi_{\omega}^2(x^p - x) + \psi_{\omega - 1}\psi_{\omega + 1}, \psi_l) = 1$, then neither $\omega$ nor $-\omega$ is an eigenvalue and again we have $t_l = 0$. Otherwise, we need to check the $y$-coordinates. The $y$-coordinate of $[\omega](x,y)$ is
\begin{align*}
\frac{\psi_{\omega + 2}\psi_{\omega - 1}^2 - \psi_{\omega - 2}\psi_{\omega + 1}^2}{4y\psi_{\omega}^3} \:,
\end{align*}
so if $\gcd(4y^{p+1}\psi_{\omega}^3 - \psi_{\omega + 2}\psi_{\omega - 1}^2 + \psi_{\omega - 2}\psi_{\omega + 1}^2, \omega_l) = 1$, then $-\omega$ is eigenvalue and $t \equiv -2\omega \pmod{l}$. Otherwise, $\omega$ is an eigenvalue and $t \equiv 2\omega \pmod{l}$.
We illustrate this method with the following example. The curve and underlying field in the example were chosen to make computations easy. Clearly, such a curve would make an extremely poor choice for a cryptosystem. However, it is illustrative, and we shall make use of this curve later as well, when we discuss Elkies and Atkin primes.
\begin{example}\label{ex:SchoofAlgorithm}
Let $E_1: y^2 = x^3 + x + 2$ be an elliptic curve, taken over $\F_{17}$. It is easy to compute by hand that
\begin{align*}
E_1(\F_{17}) &= \{\poi, (0, \pm 6), (1, \pm 2), (3, \pm 7), (4, \pm 6), (5, \pm 8), (9, \pm 3), \\
& \qquad (10, \pm 3), (11, \pm 1), (12, \pm 5), (13, \pm 6), (15, \pm 3), (16, 0)\} \:,
\end{align*}
so $|E_1(\F_{17})| = 24$. We would like to verify this using Schoof's algorithm. We need to determine the trace modulo $4\sqrt{17} \sim 16.5$, so it suffices to consider the primes 2, 3, and 5.
Consider first the case $l = 2$. We know that $t_2 = 0$ if and only if $E_1$ has a nontrivial point of order 2. Since $x^3 + x + 2 = (x + 1)(x^2 - x + 2)$ is reducible in $\F_{17}$, we conclude that there exists a nontrivial point of order 2, namely $(-1,0) = (16,0)$, and $t_2 = 0$.
Now consider the case $l = 3$, so that $p_3 = 17 \equiv 2 \pmod{3}$. Let $P = (x,y)$ be a nontrivial 3-torsion point with indeterminate coordinates. First, we compute the coordinates of $\phi_{17}(P)$ and $\phi_{17}^2(P)$ in $\F_{17}[x,y]/(f_3(x), E_1(x,y))$:
\begin{align*}
x^{17} &= -8x^3 - 2x^2 - 6x + 1, & x^{17^2} &= x, \\
y^{17} &= y\left(4x^3 - 8x^2 - 8x - 2\right), & y^{17^2} &= y.
\end{align*}
So in evaluating the test that separates Case~1 from Case~2 we see that
\begin{align*}
\gcd\left(\psi_2^2\bigl(x^{17^2} - x\bigr) + \psi_1\psi_3, \psi_3\right) = \gcd(\psi_3, \psi_3) = \psi_3 \neq 1 \:.
\end{align*}
Since also $p_3$ is not a square in $\F_3$, we mush have $t_3 = 0$. Of course, in this case, even without computing the gcd, we can immediately see that $\phi_{17}^2(P) = P = -[2]P$, so $\phi_{17}^2(P) \go [2]P = \poi$ and $t_3 = 0$. It is important to note that in general, for large primes $p$, the reductions of $x^p$, $y^p$, $x^{p^2}$, and $y^{p^2}$ would require a very significant computational effort.
Lastly, we consider the case $l = 5$. Computations here are more involved than in the previous case. To help the reader follow the algorithm, we omit many non-trivial computations. As a compensation, we provide some relevant \textsc{sage} source code to the reader in Figure~\ref{sage:Example1} in the appendix.
We have $p_5 = 17 \equiv 2 \pmod{5}$. Similar to before, let $P = (x,y)$ be a nontrivial 5-torsion point with indeterminate coordinates. Note that after reducing by the curve equation $E_1(x,y)$, the univariate 5th division polynomial evaluates to
\begin{align*}
f_5(x) = 5x^{12} - 6x^{10} - 5x^9 - 3x^8 + 4x^7 - 2x^6 + 2x^5 - 2x^4 - 6x^3 - 7x^2 + x - 7 \:.
\end{align*}
Again, we find the coordinates of $\phi_{17}(P)$ and $\phi_{17}^2(P)$ in $\F_{17}[x,y]/(f_5(x), E_1(x,y))$:
\begin{align*}
x^{17} &= -4x^{11} - 7x^{10} + x^9 - 2x^8 + 7x^7 + 5x^6 + 5x^5 - 5x^4 + 5x^2 - x + 7, \\
x^{17^2} &= -4x^{11} + 6x^{10} + 7x^9 - 3x^8 - 7x^7 + x^6 - 4x^5 - 6x^4 + 8x^3 + x^2 + 6 , \\
y^{17} &= y\left(3x^{11} + 6x^{10} + 6x^9 - 6x^8 - 3x^7 - 7x^6 + 5x^5 - 6x^4 + 2x^3 + 6x^2 + 2x + 4\right), \\
y^{17^2} &= y\left(x^{11} + 5x^{10} + 6x^9 + 4x^8 + 3x^7 - 7x^6 + 7x^5 - 5x^4 - 3x^3 + 2x^2 + 5x + 7\right).
\end{align*}
Next, we evaluate and find
\begin{align*}
\gcd\left(\psi_2^2\bigl(x^{17^2} - x\bigr) + \psi_1\psi_3, \psi_5\right) = 1 \:,
\end{align*}
so we know that Case~1 applies. Hence, we need only consider $0 < \tau \leq (5-1)/2 = 2$. Using Equation~\eqref{eq:ScalarMultiplicationWithDivisionPolynomials}, we find that
\begin{equation*}
\begin{aligned}
{} [p_5]P &= [2]P = \left(x - \frac{\psi_1 \psi_3}{\psi_2^2}, \frac{\psi_4 \psi_1^2 - \psi_0 \psi_3^2}{4y\psi_2^3}\right) \\
&= \left(x - \frac{3x^4 + 6x^2 + 24x - 1}{4y^2}, \frac{x^6 + 5x^4 + 40x^3 - 5x^2 - 8x - 33}{8y^3} \right) \:,
\end{aligned}
\end{equation*}
For simplicity define $\phi_{17}^2(P) = (x_3, y_3)$, $[2]P = (x_4, y_4)$, and $(x_3, y_3) \go (x_4, y_4) = (x_5, y_5)$. From Equation~\eqref{eq:ShortGroupLaw} we know that $x_5 = \lambda^2 - x_3 - x_4$, where $\lambda = (y_3 - y_4)/(x_3 - x_4)$. In $\F_{17}[x,y]/(f_5(x), E_1(x,y))$, this resolves to
\begin{equation*}
\lambda = y\left(-8x^{11} - 3x^{10} - 3x^9 - 3x^8 - 2x^7 - 5x^6 + x^5 - 2x^4 - 7x^3 - 8x^2 + 4x + 6 \right).
\end{equation*}
Since there are only two values of $\tau$ to check, we choose to set $\tau = 1$ and explicitly compute the $x$-coordinate equality $x_5 = \tau x^{17}$. After clearing denominators, we find that in $\F_{17}[x,y]/(f_5(x), E_1(x,y))$ the resultant expression is $h(x) \equiv 0$. Therefore, we can conclude that $t_5 = \pm 1$, and it remains to see which of the two options holds. We compute
\begin{equation*}
y_5 = y\left(-3x^{11} - 6x^{10} - 6x^9 + 6x^8 + 3x^7 + 7x^6 - 5x^5 + 6x^4 - 2x^3 - 6x^2 - 2x - 4 \right) ,
\end{equation*}
so we see immediately that $y_5 = -y^{17}$. We conclude that $t_5 = -1$.
Next we combine the above information. We have found that $t_2 = t_3 = 0$ and $t_5 = 4$. Therefore, we can uniquely determine that $t \equiv 24 \pmod{30}$. On the other hand, we know from Theorem~\ref{thm:Hasse} that $|t| \leq 2\cdot\sqrt{17} < 9$. Thus, we must have $t = -6$. It follows that $|E_1(\F_{17})| = 17 + 1 - (-6) = 24$, as needed.
\Endexample
\end{example}
The complexity of Schoof's algorithm is in the order $O(\log^{2+3\mu}p)$ bit operations \cite{Cohen-Handbook17}. Schoof \cite{Schoof-Counting} notes that although the algorithm is of polynomial running time in the logarithm of $p$, it is extremely slow and impractical. The reason for such a slow running time is due to the rapid growth in the degree of the division polynomial. For instance, Schoof \cite{Schoof-Counting} finds that if $l > 250$, then one element in the reduced polynomial ring will take more than 1.5 megabytes of memory to store.
\eccsection{Atkin's classification}\label{sec:AtkinsClassification}
As noted above, Schoof's algorithm is fairly inefficient because of the exponential growth in the degree of the division polynomial $f_l$. Atkin and Elkies sought to improve the efficiency of Schoof's algorithm by first analyzing how the restricted characteristic polynomial $\chi_l(T) = T^2 - t_lT + p_l$ of the Frobenius endomorphism splits over $\Fl$. The polynomial $\chi_l(T)$ has a root in $\Fl$ if and only if the (still unknown) discriminant $\Del_\chi = t^2 - 4p \equiv t_l^2 - 4p_l \pmod{l}$ is a square in $\Fl$. Otherwise, the roots are elements of $\Fl[\sqrt{\Del_\chi}] \cong \F_{l^2}$.
\begin{definition}\label{def:ElkiesAndAtkinPrimes}
Let $\Del_\chi = t^2 - 4p$ be the discriminant of $\chi(T)$, the characteristic polynomial of the Frobenius endomorphism. If $\Del_\chi$ is a square in $\Fl$, we say that $l$ is an \term{Elkies prime}. Otherwise, we call $l$ an \term{Atkin prime}.
\end{definition}
Atkin was able to show how the $l$-th modular polynomial $\Phi_l$ can be used to determine whether $l$ is an Elkies prime or an Atkin prime. He then proceeded to describe how to compute the order of the Frobenius endomorphism $\phi_p$ in $\PGL(\Fl)$. In the case of $l$ an Atkin prime, the order of $\phi_p$ is useful to determine possible values of the reduced trace $t_l$. In the case of $l$ an Elkies prime, Elkies was able to show how the division polynomial can be replaced by a polynomial of degree $(l-1)/2$.
The main result of this section is the classification theorem in Theorem~\ref{thm:AtkinClassification}. In order to prove the classification theorem, the following Proposition~\ref{thm:IsogenousEigenspace} will be extremely useful. Let $C_i$, with $1 \leq i \leq l+1$, be the cyclic subgroups of order $l$ of $E[l]$. Recall from Theorem~\ref{thm:ZerosOfModularPolynomial} that the zeros of $\Phi_l(x, j(E))$ are precisely the $j$-invariants of isogenous curves $\tilde{E}/C_i$ to $E$. The following theorem establishes the necessary links between the zeros of $\Phi_l(x, j(E))$ in some field extension $\F_{p^r}$, the map $\phi_p^r$, and the cyclic subgroups $C_i$.
\begin{proposition}\label{thm:IsogenousEigenspace}
Let $E$ be an ordinary elliptic curve over $\Fp$ with $j$-invariant $j \neq 0$ or 1728. Then
\begin{enumerate}
\item The polynomial $\Phi_l(x,j)$ has a zero $\tj \in \F_{p^r}$ if and only if the kernel $C$ of the corresponding isogeny $E \to E/C$ is a one-dimensional eigenspace of $\phi_p^r$ in $E[l]$, with $\phi_p$ the Frobenius endomorphism of $E$.
\item The polynomial $\Phi_l(x,j)$ splits completely in $\F_{p^r}[x]$ if and only if $\phi_p^r$ acts as a scalar matrix on $E[l]$.
\end{enumerate}
\end{proposition}
\begin{proof}
See \cite[pages 236--238]{Schoof-Counting}.
\end{proof}
In the center of the \texttt{SEA} algorithm stands the following classification theorem.
\begin{theorem}[Atkin]\label{thm:AtkinClassification}
Let $E$ be an ordinary elliptic curve defined over $\Fp$ with $j$-invariant $j \neq 0$ or 1728. Let $\Phi_l(x,j) = h_1h_2\cdots h_s$ be the factorization of $\Phi_l(x,j) \in \Fp[x]$ as a product of irreducible polynomials. Then there are the following possibilities for the degrees of $h_1, \ldots, h_s$:
\begin{enumerate}
\item $(1,1,\ldots, 1)$ or $(1,l)$. In either case we have $t^2 - 4p \equiv 0 \pmod{l}$. In the former case we set $r = 1$ and in the latter case $r = l$.
\item $(1,1,r,r, \ldots, r)$. In this case $t^2 - 4p$ is a square module $l$, $r$ divides $l-1$, and $\phi_p$ acts on $E[l]$ as a diagonal matrix $\left( \begin{smallmatrix} \lambda & 0 \\ 0 & \mu \end{smallmatrix} \right)$ with $\lambda, \mu \in \Fl^*$.
\item $(r,r, \ldots, r)$ for some $r > 1$. In this case $t^2 - 4p$ is a nonsquare modulo $l$, $r$ divides $l+1$, and the restriction of $\phi_l$ to $E[l]$ has an irreducible characteristic polynomial over $\Fl$.
\end{enumerate}
In all cases, $r$ is the order of $\phi_p$ in the projective general linear group $\PGL(\Fl)$ and the trace $t$ of the Frobenius satisfies
\begin{equation}\label{eq:RootsOfUnity}
t^2 \equiv p(\zeta + \zeta^{-1})^2 \pmod{l} \:,
\end{equation}
for some primitive $r$-th root of unity $\zeta \in \cFl$. Furthermore, the number of irreducible factors $s$ satisfies
\begin{equation}\label{eq:NumberOfIrreducibleFactors}
(-1)^s = \left(\frac{p}{l}\right) \:.
\end{equation}
\end{theorem}
\begin{proof}
Write the reduced characteristic polynomial
\begin{equation}\label{eq:CharacteristicRoots}
\chi_l(T) = T^2 - t_lT + p_l = T^2 - (\lambda + \mu)T + \lambda\mu = (T - \lambda)(T - \mu) \:.
\end{equation}
In particular, we see that $\lambda\mu \equiv p \pmod{l}$ and $\lambda + \mu \equiv t \pmod{l}$. It follows that $\Del_\chi \equiv t^2 - 4p \equiv (\lambda + \mu)^2 - 4\lambda\mu \equiv (\lambda - \mu)^2 \pmod{l}$.
From Proposition~\ref{thm:IsogenousEigenspace}, we know that the Frobenius endomorphism $\phi_p$ acts on $E[l]$ as $A$, a $2 \times 2$ matrix over $\Fl$ with a characteristic equation $\phi_p^2 - t\phi_p + p = 0$. We consider the following cases:
\begin{enumerate}
\item[1a.] $A$ is diagonalizable and has a double eigenvalue $\lambda \in \Fl^*$. Then $A$ is similar to a scalar matrix $\left(\begin{smallmatrix} \lambda & 0 \\ 0 & \lambda \end{smallmatrix}\right)$, which in $\PGL(\Fl)$ reduces to the identity matrix. Therefore, the degree of $\phi_p$ in $\PGL(\Fl)$ is 1, and $\Phi_l(x,j)$ splits completely in $\Fp$. This case corresponds to the first possibility in Theorem~\ref{thm:AtkinClassification}, with a splitting type $(1,1,\ldots, 1)$. Since $\lambda = \mu$, it is clear that $\Del_\chi \equiv t^2 - 4p \equiv (\lambda - \lambda)^2 \equiv 0 \pmod{l}$, as needed.
\item[1b.] $A$ is not diagonalizable and has eigenvalues $\lambda, \mu \in \Fl^*$. Then it must be the case that $\lambda = \mu$, or else $A$ is diagonalizable. It follows that $A$ is similar to a matrix $\left(\begin{smallmatrix} \lambda & 1 \\ 0 & \lambda \end{smallmatrix}\right)$. Then the degree of $\phi_p$ in $\PGL(\Fl)$ is $l$. This case also corresponds to the first possibility in Theorem~\ref{thm:AtkinClassification}, but here the splitting type is $(1,l)$. Here, too, $\Del_\chi \equiv t^2 - 4p \equiv (\lambda - \lambda)^2 \equiv 0 \pmod{l}$.
\item[2.] $A$ is diagonalizable and has two distinct eigenvalues $\lambda, \mu \in \Fl^*$. In particular, $\lambda^{l-1} = \mu^{l-1} = 1$. Then $A$ is similar to the matrix $\left(\begin{smallmatrix} \lambda & 0 \\ 0 & \mu \end{smallmatrix}\right)$, and the order of $\phi_p$ in $\PGL(\Fl)$ divides $l-1$. This corresponds to the second possibility in Theorem~\ref{thm:AtkinClassification}. In addition, since $\Del_\chi \equiv t^2 - 4p \equiv (\lambda - \mu)^2 \pmod{l}$ and $\lambda - \mu \in \Fl$, we conclude that $\Del_\chi$ is a square modulo $l$.
\item[3.] $A$ is not diagonalizable and has two conjugate eigenvalues $\lambda, \mu \in \F_{l^2} - \Fl$. Here, $A$ is similar to the matrix $\left(\begin{smallmatrix} 0 & 1 \\ -\lambda\mu & \lambda+\mu \end{smallmatrix}\right)$. If instead we consider the action of the Frobenius endomorphism as $\tilde{A}$, a $2 \times 2$ matrix with coefficients in $\F_{l^2}$, then $\tilde{A}$ is similar to the matrix $\left(\begin{smallmatrix} \lambda & 0 \\ 0 & \mu \end{smallmatrix}\right)$.
We claim that $\mu = \lambda^l$. To see why, let $d$ be some non-square modulo $l$. Then we can write $\lambda = \alpha + \beta\sqrt{d}$ and $\mu = \alpha - \beta\sqrt{d}$ for some $\alpha, \beta \in \Fl$. On the one hand we have $(\sqrt{d})^{2l} = (\sqrt{d})^2$, and on the other hand we have $(\sqrt{d})^l \neq \sqrt{d}$. It follows that $(\sqrt{d})^l = -\sqrt{d}$. Thus, $\lambda^l = (\alpha + \beta\sqrt{d})^l = \alpha^l + \beta^l(\sqrt{d})^l = \alpha - \beta\sqrt{d} = \mu$, as needed. Similarly, $\lambda = \mu^l$.
Let $r > 1$ be the smallest integer such that $\lambda^r \in \Fl^*$, and note that $\mu^r = (\lambda^l)^r = (\lambda^r)^l = \lambda^r$, with the last equality given since $\lambda^r \in \Fl$. In particular, $r$ is also the smallest integer such that $\mu^r \in \Fl^*$. Therefore, $\tilde{A}^l$ is a scalar matrix with coefficients in $\Fl$, and we conclude that the order of the order of the Frobenius endomorphism is $r$. The order $r$ divides $l^2 - 1$ but does not divide $l-1$. It follows that $r$ divides $l+1$.
In addition, since $\Del_\chi \equiv t^2 - 4p \equiv (\lambda - \mu)^2 \equiv 4\beta^2 d\pmod{l}$ and $d$ is a non-square in $\Fl$, we conclude that $\Del_\chi$ is also not a square modulo $l$. This corresponds to the third and final possibility in Theorem~\ref{thm:AtkinClassification}.
\end{enumerate}
We now prove Equation~\eqref{eq:RootsOfUnity}. From the discussion above we know that $r$ is the smallest integer such that $\lambda^r = \mu^r$. Recall that $\lambda\mu \equiv p \pmod{l}$ and $\lambda + \mu \equiv t \pmod{l}$. Then $\lambda^{2r} \equiv p^r \pmod{l}$, so that $\lambda^2 \equiv \zeta p \pmod{l}$ for some primitive $r$-th root of unity $\zeta \in \cFl$. Furthermore,
\begin{align*}
t^2 &\equiv (\lambda + \mu)^2 \equiv (\lambda + p/\lambda)^2 \equiv \lambda^2 + 2p + p^2\lambda^{-2} \equiv \zeta p + 2p + \zeta^{-1}p \\
&\equiv p(\zeta + \zeta^{-1})^2 \pmod{l} \:,
\end{align*}
as needed.
Lastly, for the proof of Equation~\eqref{eq:NumberOfIrreducibleFactors}, see \cite[page 240]{Schoof-Counting}.
\end{proof}
Note that Theorem~\ref{thm:AtkinClassification} is indeed a classification theorem. For each prime $l$ with $l \neq p$, we first determine the splitting type of $\Phi_l(x,j)$ by computing the degree of $g(x) = \gcd(\Phi_l(x,j), x^p - x)$. By the theorem above, the degree of $g(x)$ can only be 0, 1, 2, or $l$. If the $g(x)$ is a constant, $l$ is an Atkin prime. Otherwise it is an Elkies prime.
\begin{example}\label{ex:AtkinClassification}
Recall the elliptic curve $E_1/\F_{17}$ from the previous example. The $j$-invariant of $E_1$ is 1. The case of $l = 2$ is most easily treated by looking for points of order 2, as we did in the previous example. We shall check which for the primes 3 and 5 if they are Atkin primes or Elkies primes. Relevant \textsc{sage} source code is provided in Figure~\ref{sage:Example2} in the appendix.
Let $l = 3$. We consider the modular polynomial $\Phi_3(x,1)$ in the polynomial ring $\F_{17}[x]$. Using Section~\ref{sec:ModularPolynomials}, direct computation reveals that
\begin{align*}
\Phi_3(x,1) &= x^4 + 2618675 x^3 + 461887642896318 x^2 + 1854655034805885906044 x \\
& \quad + 1855426324856835686401 \\
& \equiv x^4 -5 x^3 + 4x^2 - x + 5 \pmod{17} \:.
\end{align*}
We use the Euclidean division algorithm to find $\gcd\left(\Phi_3(x,1), x^{17} - x\right)$, where the Euclidean domain in which we work is of course the polynomial ring $\F_{17}[x]$. The division algorithm shows that
\begin{equation*}
\Phi_3(x,1) = \left(x^3 + 7x^2 + 3x + 1\right)\left(x + 5\right) \:.
\end{equation*}
Thus, we have found a linear factor of $\Phi_3(x,1)$, so we conclude that 3 is an Elkies prime.
Now let $l = 5$. Again from Section~\ref{sec:ModularPolynomials}, the modular polynomial $\Phi_5(x,1)$ is given by
\begin{align*}
\Phi_5(x,1) &= x^6 \\
& \quad + 1718552082309 x^5 \\
& \quad + 1413658123238627268557935 x^4 \\
& \quad + 280052346791868251027764047829968560 x^3 \\
& \quad + 6729059890180623379442403339472181961775 x^2 \\
& \quad + 53010293900891930869299353688832336926727674 x \\
& \quad + 141413228178305070529031327599431299228189982721 \\
&\equiv x^6 + 6x^5 - 2x^4 + 3x^3 - 7x^2 - 6x - 8 \pmod{17}.
\end{align*}
Here, the Euclidean division algorithm reveals that $\gcd\left(\Phi_5(x,1), x^{17} - x\right) = 1$. Hence, 5 in an Atkin prime.
\Endexample
\end{example}
In the following sections we describe how the knowledge of whether $l$ is an Atkin or an Elkies prime can be used to compute the reduced trace $t_l$.
\eccsection{Atkin primes}\label{sec:AtkinPrimes}
We now turn our attention to the case of $l$ an Atkin prime and follow the treatment in \cite{Cohen-Handbook17}, \cite{Blake-Elliptic}, and \cite{Schoof-Counting}.
Our first goal is compute the degree $r$ of $\phi_p$ in $\PGL(\Fl)$. The approach Atkin took was to determine the smallest integer $i > 1$ such that
\begin{equation}\label{eq:DegreeOfFrobenius}
\gcd\left(\Phi_l(x,j), x^{p^i} - x\right) = \Phi_l(x,j) \:.
\end{equation}
Thus, $\F_{p^i}$ is the smallest field extension of $\Fp$ which contains all the roots of $\Phi_l(x,j)$. From the second statement of Proposition~\ref{thm:IsogenousEigenspace}, we conclude that $i=r$ is the degree of $\phi_p$. From Theorem~\ref{thm:AtkinClassification} we know that it suffices to check only integers $i$ that divide $l+1$ and that satisfy $(-1)^{(l+1)/i} = \left(\frac{p}{l}\right)$. The possible values of $i$ are tried with the greatest common divisor computed each time using the Euclidean algorithm.
Once the order $r$ of $\phi_p$ is determined, we need to compute the restriction modulo $l$ of the trace $t$. We shall construct a set $T_l$ of such possible values $t_l$. Equation~\eqref{eq:RootsOfUnity} is the main result we use here. There are $\euler(r)$ options for the $r$-th roots of unity $\zeta$, where $\euler$ is Euler's totient function. By symmetry, there are $\euler(r)/2$ possible values for $\zeta + \zeta^{-1}$, and from Equation~\eqref{eq:RootsOfUnity} the same is true for $t^2 \pmod{l}$. It follows that there $T_l$ includes at most $\euler(r)$ possible values of $t_l$.
Note that the primitive $r$-th roots of unity are elements of $\F_{l^2}$. To see why, let $\zeta$ be a primitive $r$-th root unity. Since $r \mid (l + 1)$, say with $ar = l+1$ for some integer $a$, we know that $\zeta^{l^2-1} = \zeta^{(l+1)(l-1)} = \zeta^{ar(l-1)} = 1$, so $\zeta \in \F_{l^2}$. Let $\lambda, \mu \in \F_{l^2} - \Fl$ be the two eigenvalues of $\phi_p$. From Proposition~\ref{thm:IsogenousEigenspace}, we know that $r$ is the smallest positive integer for which $\lambda^r = \mu^r$. It follows that $\lambda/\mu = \gamma$ is a primitive \mbox{$r$-th} root of unity. From the discussion above we conclude that $\gamma \in \F_{l^2}$. Furthermore, once we write $\F_{l^2} \cong \Fl[\sqrt{d}]$ for some nonsquare $d \in \Fl$, we can enumerate all the possible $\euler(r)$ values of $\gamma$ as follows: let $g$ be a generator for the multiplicative group of $\F_{l^2}$; then $\gamma = g^{(l^2-1)/r}$ is a primitive $r$-th root of unity, as well as any $\gamma_i = \gamma^i$ where $i$ is relatively prime to $r$ and satisfying $1 \leq i < r$.
Our next goal is to determine the members of $T_l$ using the different $\gamma_i$. From Equation~\eqref{eq:CharacteristicRoots} we know that $t \equiv \lambda + \mu \pmod{l}$ and $p \equiv \lambda\mu \pmod{l}$. Using the same nonsquare $d \in \Fl$ as above, we have $\lambda = x_1 + x_2\sqrt{d}$ and $\mu = x_1 - x_2\sqrt{d}$ for some (still unknown) $x_i \in \Fl$. Similarly, we have $\gamma_i = g_{i_1} + g_{i_2}\sqrt{d}$, but here $g_{i_1}, g_{i_2} \in \Fl$ can be computed. Additionally,
\begin{align*}
g_{i_1} + g_{i_2}\sqrt{d} &= \gamma_i = \frac{\lambda}{\mu} = \frac{\lambda^2}{\lambda\mu} = \frac{x_1^2 + dx_2^2 + 2x_1x_2\sqrt{d}}{p} \\
&= \frac{x_1^2 + dx_2^2}{p} + \frac{2x_1x_2}{p}\sqrt{d} \:.
\end{align*}
Solving for the first coordinate, we have $pg_{i_1} \equiv x_1^2 + dx_2^2 \pmod{l}$. Also, $p \equiv \lambda\mu = x_1^2 - dx_2^2 \pmod{l}$. Thus, it follows that $x_1^2 = p(g_{i_1} + 1)/2$. If $x_1^2$ is not a square in $\Fl$, then we discard $\gamma_i$ and move on to the next one. Otherwise, since $t \equiv \lambda + \mu = 2x_1 \pmod{l}$, add to $T_l$ the values $2x_1$ and $-2x_1$. We illustrate this procedure with the following example.
\begin{example}
Consider again the elliptic curve $E_1/\F_{17}$. We found in the previous example that 5 is an Atkin prime. Next, we need to compute the order $r$ of the Frobenius endomorphism $\phi_p$ in $\PGL(\Fl)$. That is, we need to find the smallest integer $i > 1$ such that Equation~\eqref{eq:DegreeOfFrobenius} holds.
From Theorem~\ref{thm:AtkinClassification} we know that we need only consider $i \mid (l+1)$. In other words, $i = 2$, $i = 3$, or $i = 6$. Furthermore, $17 \equiv 2 \pmod{5}$ is not a square in $\F_5$, so from Equation~\ref{eq:NumberOfIrreducibleFactors}, we know that $6/i$ must be odd. It follows that $i \neq 3$. The very first step in the Euclidean algorithm reveals that $\Phi_5(x,1)$ does not divide $x^{17^2} - x$. In fact, $\gcd\left(\Phi_5(x,1), x^{17^2} - x\right) = 1$. Therefore, we must have $r = i = 6$.
Next, we need to find the primitive 6th roots of unity in $\overline{\F}_5$. We know that these are elements in $\F_{5^2} \cong \F_5[\sqrt{2}]$, so we start by finding a generator $g$ for the multiplicative group $\F_5[\sqrt{2}]^*$. This group has only 24 elements, and one soon finds that $g = 3 + \sqrt{2}$ is a generator. Thus, one primitive 6th root of unity is $\gamma = g^4 = 3 + 2\sqrt{2}$ and the other is $\gamma^5 = 3 - 2\sqrt{2}$. Note that in practice, the restriction of finding $l_1, \ldots, l_r$ satisfying $\prod_{i=1}^r l_i > 4\sqrt{p}$ means that we would only evaluate small primes, say with $l_i < 1000$. Thus, it is easy to pre-compute and store generators of the multiplicative groups $\F_{l_i}[\sqrt{k_i}]^*$, where $k_i$ is a nonsquare in $\F_{l_i}$.
The two primitive 6th roots of unity are conjugates and share the same ``real'' part $g_{1_1} = g_{5_1} = 3$. So in either case, we find that $x_1^2 = 17(3 + 1)/2 \equiv 4 \pmod{5}$. Clearly, $2^2 \equiv 3^2 \equiv 4 \pmod{5}$, so $x_1 = \pm 2$. Thus, we add the two possible traces $\pm 2x_1 = \{1, 4\}$ to $T_5$.
\Endexample
\end{example}
As mentioned above, in reality one does not use the modular polynomial $\Phi_l$ in the computations, but instead would use a related polynomial. Lercier, Lubicz, and Vercauteren \cite{Cohen-Handbook17} discuss the so-called canonical modular polynomials as one example. Schoof \cite{Schoof-Counting} notes that working with modular polynomials can be done with a practical polynomial running time.
\eccsection{Elkies primes}\label{sec:ElkiesPrimes}
We know turn out attention to Elkies primes. Elkies showed that if $t^2 - 4p$ is a square modulo the prime $l$, then we may substitute the division polynomial $f_l$ of degree $(l^2-1)/2$ with a factor $F_l$ of it of degree $(l-1)/2$. This represents a very significant reduction in computation time. We now trace this procedure.
Let $E/\Fp$ be the elliptic curve under consideration and $l$ be an Elkies prime with $l \neq p$. Recall from Corollary~\ref{thm:StructureOfTorsionGroupEl} that $E[l]$ is the union of $l+1$ cyclic subgroups of order $l$, with a pair-wise intersection at the identity element. Since $l$ is an Elkies prime, we can write the restricted characteristic polynomial of the Frobenius endomorphism over $\Fl$ as
\begin{equation}\label{eq:RestrictedCharacteristicPolynomialElkies}
\chi_l(T) = T^2 - t_lT + p_l = (T - \lambda)(T - \mu) \:.
\end{equation}
Note that $t_l \equiv \lambda + \mu = \lambda + p_l/\lambda \pmod{l}$, so it suffices to find $\lambda$.
Suppose first that $\lambda = \mu$. Then $t_l \equiv 2\lambda \equiv 2\sqrt{p_l} \pmod{l}$. This corresponds to Case 2 in explanation of Schoof's algorithm in Page~\pageref{page:SchoofCaseTwo}, where we found that $\phi_p(P_1) = [\sqrt{p_l}]P_1 = [\lambda]P_1$ for some nontrivial point $P_1 \in E[l]$. That is, $\lambda$ is an eigenvalue of the Frobenius endomorphism. Let $C_1 = \langle P_1 \rangle$ be the cyclic subgroup of order $l$ generated by $P_1$. Then we have just found that $C_1$ is stable under the action of the Frobenius endomorphism: $\phi_p(C_1) = C_1$.
Now suppose that $\lambda \neq \mu$. Then from Theorem~\ref{thm:AtkinClassification}, we know that there exist nontrivial points $P_1, P_2 \in E[l]$ such that $\phi_p(P_1) = [\lambda]P_1$ and $\phi_p(P_2) = [\mu]P_2$. Let $C_1 = \langle P_1 \rangle$ and $C_2 = \langle P_2 \rangle$, and note that $C_1 \neq C_2$. We with the previous case, it follows immediately that both $C_1$ and $C_2$ are stable under the action of the Frobenius endomorphism: $\phi_p(C_1) = C_1$ and $\phi_p(C_2) = C_2$.
We shall describe in Section~\ref{sec:FactorsOfDivisionPolynomials} how this information allows for a construction of a polynomial
\begin{equation}\label{eq:ElkiesPolynomial}
F_l(x) = \!\!\!\!\!\!\! \prod_{\pm P \in C_1 \setminus \{\poi\}} \!\!\!\!\!\!\! (x - (P)_X) \:,
\end{equation}
where $(P)_X$ denotes the $x$-coordinate of $P$. Note that only one point in each pair $\pm P$ is taken, as both share the same $x$-coordinate. The degree of $F_l$ is thus $(l-1)/2$, and it is a factor of $f_l$.
From here, the algorithm proceeds in a similar way to Schoof's algorithm. We know that there exists a nonzero $\lambda \in \Fl^*$ such that for any nontrivial point $P = (x,y) \in C_1 \setminus \{\poi\}$ the equation $\phi_p(P) = [\lambda]P$ holds. Moreover, since $l$ is a prime, $\lambda$ is unique. Note that for such a point $P$ we necessarily have
\begin{align*}
x^p = x - \frac{\psi_{\lambda - 1}\psi_{\lambda + 1}}{\psi_{\lambda}^2} \:.
\end{align*}
Let $h = \psi_{\lambda}^2(x^p - x) + \psi_{\lambda - 1}\psi_{\lambda + 1}$. We shall make $h$ into a univariate equation $h_X = 0$ by reducing modulo, and substituting into, the curve equation. Then, it remains to find a value $\lambda$ such that $\gcd(h_X, F_l) \neq 1$.
As with Schoof's algorithm, it suffices to check only values $1 \leq \lambda \leq (l-1)/2$ and then test the $y$-coordinate to separate $\lambda$ from $l-\lambda$. Furthermore, we can also use the results of Theorem~\ref{thm:AtkinClassification} to narrow down further the possibilities for $\lambda$.
\begin{example}
We continue to analyze $E_1/\F_{17}$. Recall that 3 is an Elkies prime for this curve. The only two values we need to check are $\lambda = 1$ and $\lambda = 2$. We take the case $\lambda = 1$ first. In Example~\ref{ex:ElkiesPolynomial} we shall see that $F_3 = x - 2$. Therefore, we have $h = \psi_1^2(x^{17} - x) + \psi_0\psi_2 \equiv 0 \pmod{F_3}$, so indeed the correct value of $\lambda$ is 1. Then, $t = \lambda + p/\lambda \equiv 0 \pmod{3}$, as needed.
\Endexample
\end{example}
\eccsection{Factors of division polynomials}\label{sec:FactorsOfDivisionPolynomials}
In this section we describe how to construct the polynomial $F_l$ given in Equation~\eqref{eq:ElkiesPolynomial}. We shall approach this problem in two steps. First we find the first coefficient of $F_l$ (which is the sum of the roots of $F_l$, with the sign inverted). Then we use the first coefficient to compute the other coefficients of $F_l$. Throughout this section we assume that $l$ is an Elkies prime different from $p$, the characteristic of the underlying field. The discussion follows closely the ones in \cite{Blake-Elliptic} and \cite{Schoof-Counting}, though here we omit many details that are beyond the scope of this work.
Given a non-supersingular elliptic curve in a short Weierstrass equation $E/\Fp: y^2 = x^3 + a_4x + a_6$, we first compute the $j$-invariant as described in Equation~\eqref{eq:ShortJInvariant}:
\begin{equation*}
j = j_E = 1728\left(\frac{4a_4^3}{4a_4^3 + 27a_6^2}\right) \tag{\ref{eq:ShortJInvariant}}
\end{equation*}
Since $l$ is an Elkies prime, we know from Theorem~\ref{thm:AtkinClassification} that the degree of the polynomial $g(x) = \gcd(\Phi_l(x,j), x^p - x)$ is greater than zero, and that the roots of $g(x)$ are in $\Fp$. Find one of the roots and denote it by $\tj$. By Theorem~\ref{thm:ZerosOfModularPolynomial}, there exists an isogenous curve $\tilde{E}: y^2 = x^3 + \tilde{a_4}x + \tilde{a_6}$ to $E$ with $j$-invariant $\tj$. Furthermore, the kernel of the isogeny is $C$, one of the $l+1$ cyclic groups of order $l$ of $E[l]$. Our immediate goal is to find $\tilde{a_4}$ and $\tilde{a_6}$, given the knowledge of $a_4$, $a_6$, $j$, and $\tj$. This will allow us to compute the first coefficient of $F_l$.
Recall from Section~\ref{sec:DetourIntoComplexAnalysis} that any elliptic curve $E$ (with coefficients considered as integers) is characterized by a complex number $q = e^{2\pi i \tau}$. Furthermore, for an elliptic curve $E$ corresponding to the parameter $q$ as above, we have $j(q) = j_E$, where the expression on the left is from Equation~\eqref{eq:JSeries} and the one on the right is from Equation~\eqref{eq:ShortJInvariant}. In fact, the choice for the notation in Section~\ref{sec:IsomorphismAndShortWeierstrassEquations}, where the constants in Equation~\eqref{eq:EllipticConstants} were introduced, stems from the reach theory of modular forms, from which the formal sum $j(q)$ is derived. This fact gives rise to the analytical treatment we develop in this section.
For any Laurent series $f(q) = \sum_n a_n q^n$ we define $f'(q)$ to be $q\frac{\de f}{\de q} = \sum_n n a_n q^n$. Then we have the following result.
\begin{proposition}\label{thm:JPrime}
The following hold in $\Z\llbracket q\rrbracket$:
\begin{equation}\label{eq:JPrime}
\begin{aligned}
\frac{j'}{j} &= -\frac{E_6}{E_4} \:, \qquad
\frac{j'}{j-1728} = -\frac{E_4^2}{E_6} \:, \\
\vphantom{\rule{0in}{2em}}
\frac{j''}{j'} &= \frac{1}{6}E_2 - \frac{1}{2}\frac{E_4^2}{E_6} - \frac{2}{3}\frac{E_6}{E_4} \:.
\end{aligned}
\end{equation}
\end{proposition}
\begin{proof}
See \cite[page 244]{Schoof-Counting}
\end{proof}
Note that the assumption that $E/\Fp$ is an ordinary curve over a field of large characteristic ensures that the polynomials above do not vanish for the parameter $q$ associated with $E$.
The crucial observation here is that we already know from Equation~\eqref{eq:EllipticSeriesCoefficients} that $E_4(q) \equiv - 48a_4 \pmod{\BB}$ and $E_6(q) \equiv 864a_6 \pmod{\BB}$, where $\BB$ is as defined in Section~\ref{sec:DetourIntoComplexAnalysis}. Thus, we can easily find $j'$. Furthermore, we can now express $E_2$ in terms of the ratio $j''/j'$. Clearly, analogous relations exist for the (still unknown) isogenous curve $\tilde{E}: y^2 = x^3 + \tilde{a_4}x + \tilde{a_6}$, and the next theorem provides the important missing link between the invariants of both curves. It relies on the following observation: given a curve with a $j$-invariant $j(q)$, there exists an isogenous curve with a $j$-invariant $j(q^l)$ and the degree of the isogeny is $l$. As mentioned by Lercier and Morain in \cite{Lercier-Counting}, it is possible that this isogenous curve is not the one we were looking for. That is, it is possible that $\tj \neq j(q^l)$, in which case we may have to discard the curve.
\label{page:l-isogeny}
\begin{theorem}\label{thm:ModularIsogenous}
Let $l$ be a prime and $\Phi_l(x,y) \in \Z[x,y]$ be the $l$-th modular polynomial. Let $\tj(q) = j(q^l)$. Then $\Phi_l(j(q), \tj(q)) = 0$. Furthermore, the following identities of power series hold:
\begin{align} \label{eq:JPrimePartial}
\tjp &= - \frac{j'\Phi_x(j,\tj)}{l\Phi_y(j,\tj)} \:, \\
\label{eq:JDoublePrimePartial}
\frac{j''}{j'} - l\frac{\tjpp}{\tjp} &= -\frac{{j'}^2\Phi_{xx}(j,\tj) + 2lj'\tjp\Phi_{xy}(j,\tj) + l^2{\tjp}^2\Phi_{yy}(j, \tj)}{j'\Phi_x(j,\tj)} \:,
\end{align}
where the subscripts $x$ and $y$ denote partial derivatives of $\Phi_l$ with respect to those variables.
\end{theorem}
\begin{proof}
See \cite[page 246]{Schoof-Counting}.
\end{proof}
When computing the invariants in Equations~\eqref{eq:JPrimePartial} and~\eqref{eq:JDoublePrimePartial}, one must make sure that the partial derivatives do not vanish. In \cite{Schoof-Counting}, Schoof explains that this happens if $(j,\tj)$ is a singular point of $\Phi_l(x,y)$ over $\Fp$, the likelihood of which is extremely low for large values of $p$. In the case where $(j,\tj)$ is such a singular point, the curve has to be discarded and a new curve must be picked.
Equation~\eqref{eq:JPrimePartial} is used to find $\tjp$. Then, we use the first two equalities in Equation~\eqref{eq:JPrime}, as well as Equation~\eqref{eq:EllipticSeries} to find $\tilde{a_4}$, $\tilde{a_6}$, and $E_4(q^l), E_6(q^l) \pmod{\BB}$. Namely, we have
\begin{equation}\label{eq:IsogenyCoefficients}
\begin{aligned}
\tilde{a_4} &= -\frac{1}{48}\frac{{\tjp}^2}{\tj(\tj - 1728)} \:, &
\tilde{a_6} &= -\frac{1}{864}\frac{{\tjp}^3}{\tj^2(\tj - 1728)} \:, \\
E_4(q^l) &\equiv -48\tilde{a_4} \pmod{\BB} \:, &
E_6(q^l) &\equiv 864\tilde{a_6} \pmod{\BB} \:,
\end{aligned}
\end{equation}
where
\begin{equation*}
\tjp = -\frac{j'\Phi_x(j,\tj)}{l\Phi_y(j,\tj)} \:.
\end{equation*}
Next, we find $p_1$ using Equations~\eqref{eq:FirstCoefficient} and~\eqref{eq:JDoublePrimePartial}:
\begin{equation}\label{eq:FirstCoefficientFinal}
\begin{aligned}
p_1 &= \!\!\sum_{\zeta \in \mu_l, \zeta \neq 1}\!\! x(\zeta; q) \\
&= \frac{l}{2}\left(\frac{j''}{j'} - l\frac{\tjpp}{\tjp}\right) + \frac{l}{4}\left(\frac{E_4^2(q)}{E_6(q)} - l\frac{E_4^2(q^l)}{E_6(q^l)}\right) + \frac{l}{3}\left(\frac{E_6(q)}{E_4(q)} - l\frac{E_6(q^l)}{E_4(q^l)}\right) \:.
\end{aligned}
\end{equation}
Recall that our first step in computing $F_l$ is to find its first coefficient, the negated sum of its roots. Reducing $p_1$ modulo $\BB$, we have the sum of the $x$-coordinates of points in the kernel of the isogeny. But the $x$-coordinates are precisely the roots of $F_l$. Hence, we conclude that the first coefficient is $-p_1/2$.
There are two important remarks to be made here. The first is that even though the development above was complex analytic in nature, all of the computations can in fact be carried out in $\Fp$. The second remark is that in practice one does not use the modular polynomials $\Phi_l$, as their coefficients grow rapidly. There are alternative polynomials that have similar properties to the modular polynomials while having less and smaller coefficients. One example is M\"uller's modular polynomials $G_l(x,y)$ \cite{Blake-Elliptic}.
The second step is to find the rest of the coefficients of $F_l$, using the knowledge of $p_1$. Recall from Section~\ref{sec:DetourIntoComplexAnalysis} that an elliptic curve $E$ corresponds to a lattice $\Lambda = \omega_1 \Z + \omega_2 \Z$ for some $\omega_1, \omega_2 \in \C$. Let $\Lambda_1 = \omega_1 \Z + l\omega_2 \Z$ and consider the map $\C/\Lambda \to \C/\Lambda_1$ given by $z \mapsto lz$. Taking this modulo the prime ideal $\BB$, we obtain the $l$-isogeny $E \to \tilde{E}$ discussed in Page~\pageref{page:l-isogeny}.
However, Schoof finds it easier to work with a different isogeny. Define $\Lambda_2 = \frac{1}{l}\omega_1 \Z + \omega_2 \Z$ and consider the map $\C/\Lambda \to \C/\Lambda_2$ given by $z \mapsto z$. Reducing this map modulo $\BB$, we now have an isogeny $E \to E'$ for some elliptic curve $E'$. Note that $\Lambda_1 = l\Lambda_2$, so by Proposition~\ref{thm:IsomorphicLattices}, the two curves $\tilde{E}$ and $E'$ are isomorphic. Thus, the two isogenies have the same kernel, so the computation of $p_1$ is unchanged. From the equations of $g_2$ and $g_3$ in Theorem~\ref{thm:LatticeEllipticCurve} we find that $E': y^2 = x^3 + l^4\tilde{a_4}x + l^6\tilde{a_6}$.
Let $\wp(z)$ be the Weierstrass $\wp$-function associated with $\Lambda$ and write
\begin{equation*}
\wp(z) = \frac{1}{z^2} + \sum_{\omega \in \Lambda \setminus \{0\}} \frac{1}{(z - \omega)^2} - \frac{1}{\omega^2} = \frac{1}{z^2} + \sum_{k=1}^\infty c_kz^{2k}
\end{equation*}
for the Laurent series of $\wp$ at infinity. The coefficients $c_k$ are given by the following recursion:
\begin{equation}\label{eq:WeierstrassFunctionCoefficients}
\begin{aligned}
c_1 &= -\frac{a_4}{5} \:, & c_2 &= -\frac{a_6}{7} \:, &
c_k &= \frac{3}{(k-2)(2k+3)}\sum_{j=1}^{k-2}c_jc_{k-1-j} \:, \quad k \geq 3 \:.
\end{aligned}
\end{equation}
We make similar computations for the Weierstrass $\wp$-function of $\Lambda_2$ and find the corresponding coefficients $\tilde{c_i}$.
Lastly, we have this final theorem that allows us to obtain all the coefficients of $F_l$ in an efficient way.
\begin{theorem}\label{thm:ElkiesPolynomialCoefficients}
Let $l$ be prime and $F_l$ be the polynomial that vanishes on the $x$-coordinates of the points in the kernel of the isogeny $\C/\Lambda \to \C/\Lambda_2$ with lattices as defined above. Then
\begin{equation}\label{eq:ElkiesPolynomialCoefficients}
z^{l-1}F_l(\wp(z)) = \exp\left(-\frac{1}{2}p_1z^2 - \sum_{k=1}^\infty \frac{\tilde{c_k} - lc_k}{(2k+1)(2k+2)}z^{2k+2}\right) \:.
\end{equation}
\end{theorem}
\begin{proof}
See \cite[page 252]{Schoof-Counting}
\end{proof}
By expanding the expressions on both sides of Equation~\eqref{eq:ElkiesPolynomialCoefficients}, we can find the coefficients of $F_l(x) = x^{(l-1)/2} + a_{(l-3)/2}x^{(l-3)/2} + \cdots + a_0$. We give here the first three:
\begin{align*}
a_{(l-3)/2} &= -\frac{p_1}{2} \:, \\
a_{(l-5)/2} &= \frac{p_1^2}{8} - \frac{\tilde{c_1} - lc_1}{12} - \frac{l-1}{2}c_1 \:, \\
a_{(l-7)/2} &= -\frac{p_1^3}{48} - \frac{\tilde{c_2} - lc_2}{30} + \frac{\tilde{c_1} - lc_1}{24}p_1 - \frac{l-1}{2}c_2 + \frac{l-3}{4}c_1p_1 \:.
\end{align*}
Schoof \cite{Schoof-Counting} remarks that the denominators in the expressions for $a_i$ are products of small primes. Thus, over a large prime field there is no risk that the denominators will vanish.
\begin{example}\label{ex:ElkiesPolynomial}
We continue with the same curve $E_1/\F_{17}$ as in the previous examples. In this example we find $F_3$. We recall the following facts: (i) 3 is an Elkies prime for this curve; (ii) the $j$-invariant of $E_1$ is 1; and (iii) $\gcd(\Phi_3(x,1), x^{17} - x) = x + 5$. Note that the degree of $F_3$ is $(3-1)/2 = 1$, so only one coefficient, $-p_1/2$, needs to be found.
First we use Equations~\eqref{eq:EllipticSeries} and~\eqref{eq:JPrime} to find
\begin{align*}
E_4(q) &\equiv 3 \pmod{\BB} \:, & E_6(q) &\equiv -6 \pmod{\BB} \:, & j' &= 2 \:.
\end{align*}
From the $\gcd$ above, we know that we must set $\tj = -5$. Next, we compute
\begin{align*}
\Phi_x(j,\tj) &\equiv -1 \pmod{17}\:, & \Phi_y(j,\tj) &\equiv 2 \pmod{17}\:.
\end{align*}
Using Equation~\eqref{eq:JPrimePartial} and then~\eqref{eq:IsogenyCoefficients}, we find
\begin{align*}
\tjp &\equiv 6 \pmod{17} \:, & E_4(q^l) &\equiv 3 \pmod{\BB} \:, & E_6(q^l) &\equiv 7 \pmod{\BB} \:.
\end{align*}
In particular, the isogenous curve is $\tilde{E}: y^2 = x^3 + x - 8$.
The next step is to find $j''/j' - l\tjpp/\tjp$ using Equation~\eqref{eq:JDoublePrimePartial}. We first compute
\begin{align*}
\Phi_{xx}(j,\tj) &\equiv 6 \pmod{17}\:, & \Phi_{xy}(j,\tj) &\equiv -2 \pmod{17} \:, &\Phi_{yy}(j,\tj) &\equiv -1 \pmod{17} \:.
\end{align*}
It follows that
\begin{align*}
\frac{j''}{j'} - l\frac{\tjpp}{\tjp} &\equiv - 1 \pmod{17} \:.
\end{align*}
To assist in the computations above, some relevant \textsc{sage} source code is provided in Figure~\ref{sage:Example5} in the appendix.
Now we can find $p_1 = 4$ using Equation~\eqref{eq:FirstCoefficientFinal}. Therefore, $F_3 = x - 2$.
\Endexample
\end{example}
\eccsection{Combining information}\label{sec:CombiningInformation}
The final step in the algorithm is to combine the information given to us by the Atkin and Elkies procedures. Unlike Schoof's original algorithm, the Chinese remainder theorem does not suffice here. The reason is that Atkin's procedure provides us with a \emph{set} $T_l$ of possible traces for each Atkin prime $l$, rather than a unique trace. Therefore another approach must be taken.
One possibility is to consider more primes $l_i$ than the minimum needed by the condition $\prod_{i=1}^r l_i > 4\sqrt{p}$ until there are sufficiently many primes to recover the trace $t$. However, in practice a variant of the so-called \term{baby-step/giant-step (BSGS)} algorithm is taken, which allows to compute $t$ modulo the product of the Atkin primes.
The BSGS algorithm, due to Shanks, is a time/space tradeoff algorithm and is one of the generic methods of solving the DLP. As explained in \cite{Blake-Elliptic}, the algorithm's running time is in the order of $O(\sqrt{n})$, where $n$ is the order of the underlying abelian group. In this algorithm, one first computes a set of values (baby steps) and stores them in a table. With the running time assumption as above, the space needed for the table is also in the order of $O(\sqrt{n})$. Next one computes another set of values (giant steps), each time comparing the current value with the ones stored in table. When a match is found, the algorithm terminates and the DLP can be solved. The variant used in the \texttt{SEA} algorithm is explained in much more detail below.
We follow the discussion in \cite{Blake-Elliptic}. To find the trace $t$, we first compute the trace $t_E$ modulo the product $m_E$ of the Elkies primes. This is done using the Chinese remainder theorem. Next, we split the set of Atkin primes into two, one with a product $m_1$ and the other with a product $m_2$.
Using the Chinese remainder theorem on each of these sets, we construct two sets $S_1$ and $S_2$ such that
\begin{align*}
t &\equiv t_1 \pmod{m_1} \text{ with } t_1 \in S_1 \:, &
t &\equiv t_2 \pmod{m_2} \text{ with } t_2 \in S_2 \:.
\end{align*}
We choose the sets such that the each one has approximately the same number of possible traces modulo the corresponding product $m_1$ or $m_2$.
Therefore, we can write
\begin{equation}\label{eq:BabyStepGiantStep}
t = t_E + m_E(m_1r_2 + m_2r_1)
\end{equation}
for some integers $r_1$ and $r_2$. Taking the above equation modulo $m_1$, we see that $t_1 \equiv t_E + m_Em_2r_1 \pmod{m_1}$. Similarly we can reduce modulo $m_2$ and find that
\begin{equation}\label{eq:ConditionsOnBSGS}
\begin{aligned}
r_1 &\equiv \frac{t_1 - t_E}{m_Em_2} \pmod{m_1} \:, &
r_2 &\equiv \frac{t_2 - t_E}{m_Em_1} \pmod{m_2} \:. &
\end{aligned}
\end{equation}
Of course, the exact values of $t_1$ and $t_2$ is not yet known. The procedure henceforth is to determine $r_1$ and $r_2$ and the recover $t$ using Equation~\eqref{eq:BabyStepGiantStep}. This procedure is reasonably fast due to the following lemma, which establishes a bound on the sizes of $r_1$ and $r_2$.
\begin{lemma}\label{thm:BoundBSGS}
Consider Equation~\eqref{eq:BabyStepGiantStep}. If we choose $0 \leq t_E < m_E$ and $|r_1| \leq \lfloor \frac{m_1}{2} \rfloor$, then $|r_2| \leq m_2$.
\end{lemma}
\begin{proof}
We can rewrite Equation~\eqref{eq:BabyStepGiantStep} to have $r_2 = \frac{t - t_E - m_Em_2r_1}{m_Em_1}$. Then, recalling that by assumption $m_Em_1m_2 > 4\sqrt{p}$ and $|t| \leq 2\sqrt{p}$,
\begin{align*}
|r_2| &\leq \frac{|t| + |t_E| + m_Em_2|r_1|}{m_Em_1} \leq \frac{2\sqrt{p}}{m_Em_1} + \frac{1}{m_1} + \frac{m_2}{2} \\
&\leq \frac{m_2}{2} + \frac{1}{m_1} + \frac{m_2}{2} = m_2 + \frac{1}{m_1} \:.
\end{align*}
Since $m_1$, $m_2$, and $r_2$ are all integers, it follows that $|r_2| \leq m_2$, as needed.
\end{proof}
Recall that the order of group $E(\Fp)$ is $p + 1 - t$. Thus, for any $\Fp$-rational point $P$ of $E$, we have $[p+1]P = [t]P = [t_E + m_E(m_1r_2 + m_2r_1)]P$. Therefore, we can write $[p + 1 - t_E]P - [r_1m_2m_E]P = [r_2m_1m_E]P$. We shall consider the expression on the left-hand side as the one defining the baby steps. The expression on the right is the one defining the giant steps.
Specifically, we first pick a random point $P$ on $E/\Fp$. Then we go over the possible values of $t_1$. For each such value, we use Equation~\eqref{eq:ConditionsOnBSGS} to choose $r_1$ such that $|r_1| \leq \lfloor \frac{m_1}{2} \rfloor$. The next step is to compute $Q_{r_1} = [p + 1 - t_E]P - [r_1m_2m_E]P$ and store the tuple $(Q_{r_1}, r_1)$ in a table. It is important to keep the table sorted to speed up the procedure. Up to here is the analogue of the baby step part.
Next, we iterate over the possible values of $t_2$. From Lemma~\ref{thm:BoundBSGS} we only that the value of $r_2$ we seek satisfies $|r_2| \leq m_2$. We also know that $r_2$ satisfies Equation~\eqref{eq:ConditionsOnBSGS}. This allows us to construct a set $R_2^{t_2}$ of possible $r_2$ values corresponding to $t_2$. For each such possible value, we compute $Q_{r_2}' = [r_2m_1m_E]P$ and compare it to the values we stored in the table. We continue until a match is found.
Once a match is found, we can recover the value $t$ from Equation~\eqref{eq:BabyStepGiantStep}. Then, the order of the group of $\Fp$-rational points is determined from Hesse's equation~\eqref{eq:Hasse}. Blake, Seroussi, and Smart \cite{Blake-Elliptic} note that in practice there are still some tests to be made to make sure we indeed have the correct group order and that the group suffices for cryptographic purposes.
\eccsection{Complete \texttt{SEA} algorithm}\label{sec:CompleteSEAAlgorithm}
The running time of the \texttt{SEA} algorithm is in the order of $O(\log^{2 + 2\mu}p)$ and the storage requirement is in the order of $O(\log^2 p)$, as discussed in \cite{Cohen-Handbook17}.
We provide here the full \texttt{SEA} algorithm in pseudo-code, adapted from and expanded on the one in \cite{Blake-Elliptic}. The algorithm we provide is not efficient, in the sense that some of the computations are done multiple times and the use of method parameters is redundant and space-consuming. This was done to keep the important parts of the algorithm free of unnecessary clutter.
The main \texttt{SEA} algorithm is as given in Figure~\ref{alg:SEAAlgorithm}, where the first step of the Elkies procedure (\textit{i.e.}, finding a factor of the division polynomial) is the algorithm given in Figure~\ref{alg:FactorOfDivisionPolynomial}.
We assumed that we have functions with the following signatures:
\begin{enumerate} \sf
\item \texttt{NextPrime}$(p)$ \\
Input: A prime $p$. \\
Output: The smallest prime number larger than $p$.
\item \texttt{FindNonSquareInFiniteField($l$)} \\
Input: A prime $l$. \\
Output: An integer $0 < d < l$ with $\left(\frac{d}{l}\right) = -1$.
\item \texttt{GeneratorOfMultiplicativeGroup}$(l, d)$ \\
Input: A prime $l$ and an integer $d$ with $\left(\frac{d}{l}\right) = -1$. \\
Output: A generator $g$ of $\Fl[\sqrt{d}]^*$.
\end{enumerate}
\begin{figure}[H] \hrule \ \\ \sf
\texttt{GetFactorOfDivisionPolynomial}$(l, E, p)$ \\
Input: An Elkies prime $l$ and an elliptic curve $E$ over a prime field $\Fp$. \\
Output: A factor $F_l(x)$ of degree $d = (l-1)/2$ of $f_l(x)$. \hrule
\begin{tabbing}
\phantom{0}1. \quad determine $j$ from Equation~(\ref{eq:ShortJInvariant}) \\
\phantom{0}2. \quad determine $E_4(q), E_6(q) \mod{\BB}$ from Equation~(\ref{eq:EllipticSeries}) \\
\phantom{0}3. \quad determine $j'$ from Equation~(\ref{eq:JPrime}) \\
\phantom{0}4. \quad $\tj \leftarrow $ a root of $\Phi_l(x,j)$ in $\Fp$ \\
\phantom{0}5. \quad determine $\tjp$ from Equation~(\ref{eq:JPrimePartial}) \\
\phantom{0}6. \quad determine $j''/j' - l\tjpp/\tjp$ from Equation~(\ref{eq:JDoublePrimePartial}) \\
\phantom{0}7. \quad determine $E_4(q^l), E_6(q^l) \mod{\BB}$ from Equation~(\ref{eq:IsogenyCoefficients}) \\
\phantom{0}8. \quad determine $p_1$ from Equation~(\ref{eq:FirstCoefficientFinal}) \\
\phantom{0}9. \quad determine $c_k$ and $\tilde{c_k}$ for $k \leq d$ from Equation~(\ref{eq:WeierstrassFunctionCoefficients}) \\
10. \quad determine $F_l$ from Equation~(\ref{eq:ElkiesPolynomialCoefficients}) \\
11. \quad \textbf{return} $F_l(x)$
\end{tabbing} \hrule \rm
\caption{Factor of division polynomial\label{alg:FactorOfDivisionPolynomial}}
\end{figure}
\begin{figure}[H] \hrule \ \\ \sf
\texttt{SchoofElkiesAtkinAlgorithm}$(E, p)$ \\
Input: An elliptic curve $E$ over a prime field $\Fp$. \\
Output: The order of $E(\Fp)$. \hrule
\begin{tabbing}
\phantom{0}1. \quad $M \leftarrow 1$, $l \leftarrow 2$, $A_p \leftarrow \{\}$, $E_p \leftarrow \{\}$ \\
\phantom{0}2. \quad determine $j$ from Equation~(\ref{eq:ShortJInvariant}) \\
\phantom{0}3. \quad \textbf{while} $M < 4\sqrt{p}$ \textbf{do} \\
\phantom{0}4. \quad \tabspace \textbf{if} $\deg(\gcd(\Phi_l(x,j), x^p - x)) = 0$ \textbf{then} \phantom{\textbf{else}} \tabspace\tabspace // Atkin prime \\
\phantom{0}5. \quad \tabspace\tabspace $T \leftarrow \{\}$ \\
\phantom{0}6. \quad \tabspace\tabspace determine $r$ from Theorem~\ref{thm:AtkinClassification} \\
\phantom{0}7. \quad \tabspace\tabspace $d \leftarrow \texttt{FindNonSquareInFiniteField}(l)$ \\
\phantom{0}8. \quad \tabspace\tabspace $g \leftarrow \texttt{GeneratorOfMultiplicativeGroup}(l, d)$ \\
\phantom{0}9. \quad \tabspace\tabspace $S \leftarrow \{g^{i(l^2-1)/r} \mid \gcd(i,r) = 1\}$ \\
10. \quad \tabspace\tabspace \textbf{for each} $\gamma_i \in S$ \textbf{do} \\
11. \quad \tabspace\tabspace\tabspace write $\gamma_i = g_{i_1} + \sqrt{d}g_{i_2}$ \\
12. \quad \tabspace\tabspace\tabspace $z \leftarrow p(g_{i_1} + 1)/2 \pmod{l}$ \\
13. \quad \tabspace\tabspace\tabspace \textbf{if} $\left(\frac{z}{l}\right) = 1$ \textbf{then} \\
14. \quad \tabspace\tabspace\tabspace\tabspace $x \leftarrow \sqrt{z} \pmod{l}$ \\
15. \quad \tabspace\tabspace\tabspace\tabspace $T \leftarrow T \cup \{2x, -2x\}$ \\
16. \quad \tabspace\tabspace $A_p \leftarrow A_p \cup (T,l)$ \\
17. \quad \tabspace \textbf{else} \phantom{\textbf{if} $\deg(\gcd(\Phi_l(x,j), x^p - x)) = 0$ \textbf{then}} \tabspace\tabspace // Elkies prime \\
18. \quad \tabspace\tabspace $F_l(x) \leftarrow \texttt{GetFactorOfDivisionPolynomialFactor}(l, E, p)$ \\
19. \quad \tabspace\tabspace find $\lambda$ such that $\gcd(\psi_\lambda^2(x^p - x) + \psi_{\lambda-1}\psi_{\lambda+1}, F_l(x)) \neq 1$ \\
20. \quad \tabspace\tabspace $t \leftarrow \lambda + \lambda/p \pmod{l}$ \\
21. \quad \tabspace\tabspace $E_p \leftarrow E_p \cup \{(t, l)\}$ \\
22. \quad \tabspace $M \leftarrow M \times l$ \\
23. \quad \tabspace $l \leftarrow \texttt{NextPrime}(l)$ \\
24. \quad recover $t$ using the sets $A_p$ and $E_p$, as explained in Section~\ref{sec:CombiningInformation} \\
25. \quad \textbf{return} $p + 1 - t$
\end{tabbing} \hrule \rm
\caption{\texttt{SEA} algorithm\label{alg:SEAAlgorithm}}
\end{figure}
\appendix
%================================================================================
\eccpart{Appendix}\label{sec:Appendix}
%================================================================================
We present in the appendix \textsc{sage} code that was applied in Examples~\ref{ex:SchoofAlgorithm},~\ref{ex:AtkinClassification}, and~\ref{ex:ElkiesPolynomial}.
\begin{figure}[H] \hrule \ \scriptsize
\begin{verbatim}
sage: #== General Definitions ==#
sage: R = IntegerModRing(17)
sage: x = PolynomialRing(GF(17), 'x').gen()
sage: E1 = EllipticCurve([GF(17)(0),0,0,1,2]); E1
Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 17}
sage: j = E1.j_invariant(); j
1
sage: P1 = PolynomialRing(GF(17), 'x'); x = P1.gen()
sage: f5 = 5*x^12 - 6*x^10 - 5*x^9 - 3*x^8 + 4*x^7 - 2*x^6 + 2*x^5 - 2*x^4 - 6*x^3 - 7*x^2 + x - 7
sage: # F_{17}[a]/(f_5) is the univariate ring we work over.
sage: # It is not taken modulo the curve equation, so we have to carry the y's manually.
sage: F17f5 = P1.quotient(f5, 'a'); a = F17f5.gen(); F17f5
Univariate Quotient Polynomial Ring in a over Finite Field of size 17 with modulus 5*x^12
+ 11*x^10 + 12*x^9 + 14*x^8 + 4*x^7 + 15*x^6 + 2*x^5 + 15*x^4 + 11*x^3 + 10*x^2 + x + 10
sage: #== Computing lambda ==#
sage: # numeratorOfLambda is the numerator of lambda, divided by y
sage: numeratorOfLambda = 32*(a^3 + a + 2)^((17^2+3)/2) - 4*(a^6 + 5*a^4 + 40*a^3 - 5*a^2 - 8*a - 33)
sage: denominatorOfLambda = 32*(a^3 + a + 2)^2*(a^(17^2) - a) + 8*(a^3 + a + 2)*(3*a^4 + 6*a^2 + 24*a - 1)
sage: # lambda5 is lambda, divided by y
sage: lambda5 = numeratorOfLambda/denominatorOfLambda; lambda5
9*a^11 + 14*a^10 + 14*a^9 + 14*a^8 + 15*a^7 + 12*a^6 + a^5 + 15*a^4 + 10*a^3 + 9*a^2 + 4*a + 6
sage: #== Computing the expression for y_5 ==#
sage: # y5 is y_5, divided by y
sage: y5 = lambda5*(2*a^(17^2) - lambda5^2*(a^3 + a + 2) + a - (3*a^4 + 6*a^2 + 24*a - 1)
/(4*(a^3 + a + 2))) - (a^3 + a + 2)^((17^2-1)/2); y5
14*a^11 + 11*a^10 + 11*a^9 + 6*a^8 + 3*a^7 + 7*a^6 + 12*a^5 + 6*a^4 + 15*a^3 + 11*a^2 + 15*a + 13
sage: #== Comparing y_5 with y^{17} ==#
sage: (a^3 + a + 2)^8 + y5
0
\end{verbatim} \hrule
\caption{Example 1 (\textsc{sage} code)\label{sage:Example1}}
\end{figure}
\begin{figure}[H] \hrule \ \scriptsize
\begin{verbatim}
sage: # Phi_3(x,j=1):
sage: c1 = R(2232)
sage: c2 = R(-1069956)
sage: c3 = R(3686400)
sage: c4 = R(2587918086)
sage: c5 = R(8900222976000)
sage: c6 = R(452984832000000)
sage: c7 = R(-770845966336000000)
sage: c8 = R(1855425871872000000000)
sage: a4 = 1 # Coefficient of x^4
sage: a3 = R(-1+c1+c2+c3) # Coefficient of x^3
sage: a2 = R(c1+c4+c5+c6) # Coefficient of x^2
sage: a1 = R(c2+c5+c7+c8) # Coefficient of x
sage: a0 = R(1+c3+c6+c8) # Scalar
sage: Phi3 = a4*x^4 + a3*x^3 + a2*x^2 + a1*x + a0; Phi3
x^4 + 12*x^3 + 4*x^2 + 16*x + 5
sage: # This shows that Phi_3 is an Elkies prime for E_1.
sage: # The root of the linear factor is the j-invariant of an isogenous curve.
sage: Phi3.factor()
(x + 5) * (x^3 + 7*x^2 + 3*x + 1)
sage: # Phi_5(x,j=1):
sage: d1 = R(3720)
sage: d2 = R(-4550940)
sage: d3 = R(2028551200)
sage: d4 = R(-246683410950)
sage: d5 = R(1963211489280)
sage: d6 = R(1665999364600)
sage: d7 = R(107878928185336800)
sage: d8 = R(383083609779811215375)
sage: d9 = R(128541798906828816384000)
sage: d10 = R(1284733132841424456253440)
sage: d11 = R(-441206965512914835246100)
sage: d12 = R(26898488858380731577417728000)
sage: d13 = R(-192457934618928299655108231168000)
sage: d14 = R(280244777828439527804321565297868800)
sage: d15 = R(5110941777552418083110765199360000)
sage: d16 = R(36554736583949629295706472332656640000)
sage: d17 = R(6692500042627997708487149415015068467200)
sage: d18 = R(-264073457076620596259715790247978782949376)
sage: d19 = R(53274330803424425450420160273356509151232000)
sage: d20 = R(141359947154721358697753474691071362751004672000)
sage: b6 = 1 # Coefficient of x^6
sage: b5 = R(-1+d1+d2+d3+d4+d5) # Coefficient of x^5
sage: b4 = R(d1+d6+d7+d8+d9+d10) # Coefficient of x^4
sage: b3 = R(d2+d7+d11+d12+d13+d14) # Coefficient of x^3
sage: b2 = R(d3+d8+d12+d15+d16+d17) # Coefficient of x^2
sage: b1 = R(d4+d9+d13+d16+d18+d19) # Coefficient of x
sage: b0 = R(1+d5+d10+d14+d17+d19+d20) # Scalar
sage: Phi5 = b6*x^6 + b5*x^5 + b4*x^4 + b3*x^3 + b2*x^2 + b1*x + b0; Phi5
x^6 + 6*x^5 + 15*x^4 + 3*x^3 + 10*x^2 + 11*x + 9
sage: # This shows that 5 is an Atkin prime for E_1.
sage: gcd(Phi5, x^17 - x)
1
\end{verbatim} \hrule
\caption{Example 2 (\textsc{sage} code)\label{sage:Example2}}
\end{figure}
\begin{figure}[H] \hrule \ \scriptsize
\begin{verbatim}
sage: #== Finding the partial derivatives of Phi_3, evaluated at j = 1 and \tilde{j} = -5 ==#
sage: tj = R(-5)
sage: Phi3x = R(4*j^3 - 3*j^2*tj^3 + 3*c1*j^2*tj^2 + 2*c1*j*tj^3 + 3*c2*j^2*tj + c2*tj^3
+ 3*c3*j^2 + 2*c4*j*tj^2 + 2*c5*j*tj + c5*tj^2 + 2*c6*j + c7*tj + c8); Phi3x
16
sage: Phi3y = R(4*tj^3 - 3*tj^2*j^3 + 3*c1*tj^2*j^2 + 2*c1*tj*j^3 + 3*c2*tj^2*j + c2*j^3
+ 3*c3*tj^2 + 2*c4*tj*j^2 + 2*c5*tj*j + c5*j^2 + 2*c6*tj + c7*j + c8); Phi3y
2
sage: Phi3xx = R(12*j^2 - 6*j*tj^3 + 6*c1*j*tj^2 + 2*c1*tj^3 + 6*c2*j*tj + 6*c3*j + 2*c4*tj^2
+ 2*c5*tj + 2*c6); Phi3xx
6
sage: Phi3yy = R(12*tj^2 - 6*tj*j^3 + 6*c1*tj*j^2 + 2*c1*j^3 + 6*c2*tj*j + 6*c3*tj + 2*c4*j^2
+ 2*c5*j + 2*c6); Phi3yy
16
sage: Phi3xy = R(-9*j^2*tj^2 + 6*c1*j^2*tj + 6*c1*j*tj^2 + 3*c2*j^2 + 3*c2*tj^2 + 4*c4*j*tj
+ 2*c5*j + 2*c5*tj + c7); Phi3xy
15
\end{verbatim} \hrule
\caption{Example 5 (\textsc{sage} code)\label{sage:Example5}}
\end{figure}
\pagebreak
\bibliography{bib-SchoofElkiesAtkinAlgorithm}
\end{document}