%\documentclass[10pt,presentation]{beamer}
\documentclass[10pt,handout]{beamer}
\usepackage{kbexoslide}
\usepackage{extarrows}
\DeclareMathOperator{\car}{car}
\newcommand{\red}[1]{\color{red}#1\color{black}}

\title{Primalité et factorisation des entiers}

\begin{document}
\begin{frame}
\titlepage
\end{frame}

\begin{frame}
\tableofcontents
\end{frame}

\section{Introduction}
\begin{frame}
Soit $N > 1$ un entier. Nous considérons 3 problèmes «élémentaires» :

\begin{enumerate}
\item (Primalité) En supposant que $N$ est premier, le prouver.
\item (Non primalité) En supposant que $N$ est composé, le prouver.
\item (Factorisation) En supposant que $N$ est composé, trouver un facteur
non trivial $d\mid N$, $d \neq 1, N$.
\end{enumerate}
Ils permettent de résoudre le problème global de la factorisation complète :
\begin{enumerate}\setcounter{enumi}{3}
\item Factoriser $N$ complètement: déterminer les diviseurs premiers $p$
de $N$, et pour chacun d'entre eux afficher $v_p(N)$ et une preuve de
primalité.
\end{enumerate}

En pratique, $(2)$ est très facile, $(1)$ admet une solution raisonnable, et
$(3)$ est toujours largement ouvert.
\end{frame}

\begin{frame}
\begin{theo}[Rabin, 1980] (2) est résolu en temps probabiliste
$\Ot(\log N)^2$.
\end{theo}

\begin{theo}[Agrawal-Kayal-Saxena, 2002] (1) et (2) sont résolus en temps
déterministe $O(\log N)^{10.5}$.
\end{theo}
Lenstra et Pomerance ont amélioré l'estimation (et l'algorithme):
$O_\e(\log N)^{6 +\e}$ mais la constante du $O$ n'est plus effective si $\e >
0$ est trop petit!

\begin{theo}[Miller, 1976] En supposant une Hypothèse de Riemann convenable,
(1) et (2) sont résolus en temps $\Ot(\log N)^4$.
\end{theo}
C'est un enoncé prouvé mais \red{conditionnel}!
\end{frame}

\begin{frame}
\begin{guess}[Goldwasser-Killian 1986, Atkin-Morain 1993, Shallit $\approx
1990$] L'algorithme ECPP (Elliptic Curves Primality Proving) résout (1) en
temps probabiliste $\Ot(\log N)^4$.
\end{guess}
C'est bien une \red{conjecture}! Par contre, si l'algorithme s'arrête, il
produit une \emph{preuve} (ou certificat) de primalité: un algorithme
auxiliaire permettant de vérifier rapidement la primalité de $N$.
\end{frame}

\begin{frame}
\def\a{\alpha}
\begin{defi} Soit $0\leq \a\leq 1$, on définit
$$ L_\a(N) = \exp \big((\log N)^{\a}(\log\log N)^{1-\a}\big). $$
N.B. On a $L_0(N) = \log N$ et $L_1(N) = N$.
\end{defi}
\begin{theo}[Dixon, 1981] 
L'entier $N$ est factorisé en temps probabiliste $L_{1/2}(N)^{O(1)}$.
\end{theo}
\begin{guess}[Pollard, 1988]
Le crible algébrique (NFS) factorise $N$ en temps probabiliste
$L_{1/3}(N)^{O(1)}$.
\end{guess}

Record actuel (2020) pour un entier type RSA : 250 chiffres
\end{frame}

\section{Non-primalité}
\begin{frame}
\begin{theo}\label{th:primcong} Si $N > 2$ est premier et $0 < a < N$, alors
on a dans $\ZM/N\ZM$:
\begin{enumerate}
\item $a^{N-1} = 1$;
\item Écrivons $N - 1 = 2^e q$ où $q$ impair et $e \geq 1$ et posons
 $b := a^q$. Alors $b = 1$ ou il existe un unique indice
 $0\leq i < e$ tel que $b^{2^i} = -1$.
\end{enumerate}
\end{theo}
\begin{proof} (1) est le test de Fermat (1640).
(2) (Rabin-Miller) suit de l'identité polynomiale
$$ X^{2^e} - 1 = \prod_{d\mid 2^e}\Phi_d(X) = (X - 1)(X+1)(X^2 + 1)\dots(X^{2^{e-1}} + 1) $$
évaluée en $X = b$.
\end{proof}
\end{frame}

\begin{frame}
\textbf{Test probabiliste:} on tire $a\in ]0,N[$ uniformément au hasard (et
indépendamment des tests précédents) et on vérifie (1) ou (2). Si l'assertion
n'est pas vérifiée pour le $a$ choisi, alors $N$ est \red{composé}. Un tel $a$
est appelé \red{témoin}. N.B. Si $a$ est témoin pour le test de Fermat alors
il l'est aussi pour Rabin-Miller.
\begin{alertblock}{Complexité}
$O(\log N)^3$ opérations binaires.
\end{alertblock}
\end{frame}

\begin{frame}
\begin{theo}[Korselt, 1899]
Si $N > 1$ est composé, alors
$$ \set{0 < a < N\colon a^{N-1} \equiv 1 \pmod{N}} $$
est un sous-groupe de $(\ZM/N\ZM)^*$. Il est égal à $(\ZM/N\ZM)^*$ tout entier
si et seulement si $N$ est sans facteurs carrés et $p\mid N\Rightarrow
p-1\mid N$ pour tout diviseur premier $p$ de $N$.
\end{theo}
Par exemple 561, 1105, 1729, 2465\dots Il y en a une infinité. Si le
sous-groupe est d'indice $\geq 2$, au moins $50\%$ des $a$ sont témoins pour
le test de Fermat.
\end{frame}

\begin{frame}
\begin{theo}[Rabin, 1980]
Si $N > 1$ est composé, un $a\in]0,N[$ uniforme est témoin pour le test de
Rabin-Miller avec probabilité $\geq 3/4$.
\end{theo}

\begin{theo}[Burthe, 1997]
La moyenne des plus petit témoins quand $N$ parcourt les entiers composés
impairs $\leq X$ est $2 + o(1)$.
\end{theo}
\end{frame}

\section{Primalité}

\begin{frame}{Preuve de primalité}

L'idée est la suivante: $N > 1$ est premier si et seulement si
$(\ZM/N\ZM)^*$ est cyclique d'ordre $N-1$. Il suffit donc d'exhiber un
élément $a\in (\ZM/N\ZM)^*$ d'ordre $N-1$. Il faut que $a^{N-1} = 1$ et
$\pgcd(a^{(N-1)/p}-1, N)\neq 1$ pour tout diviseur premier $p$ de $N-1$.

En fait, le même test élémentaire permet de faire mieux:
\begin{theo}[Pocklington, 1914]\label{th:pock} Soit $N>1$ un entier et
$p\mid N-1$ un \emph{premier} tel que $v_p(N-1) = e$. On suppose que 
l'entier $a$ satisfait
\begin{itemize}
\item $a^{N-1} \equiv 1 \pmod{N}$,
\item $\pgcd(a^{(N-1)/p}-1, N) = 1$.
\end{itemize}
Alors tout diviseur $d\mid N$ vérifie $d \equiv 1\pmod{p^e}$.
\end{theo}
\end{frame}

\begin{frame}
\begin{proof} On peut supposer que $d$ est premier, puisqu'un produit
d'entiers $\equiv 1\pmod{M}$ est congru à $1\pmod{M}$. Puisque
$d\mid N$, on a $a^{N-1} \equiv 1 \pmod{d}$, qui implique que $\pgcd(a,d) =
1$ et donc $a^{d-1}\equiv 1\pmod{d}$ (Fermat).

Puisque $a^{(N-1)/p}\not\equiv 1\pmod{d}$, l'ordre $r$ de $a$ dans
$(\ZM/d\ZM)^*$ vérifie $r\mid N-1$, mais $r\nmid (N-1)/p$, et donc
$p^e \mid r$. On conclut puisque $r \mid d-1$.
\end{proof}

\begin{coro} Soit $N > 1$ un entier. Supposons $N - 1 = FU$ avec $F\geq
\sqrt{N}$, où les diviseurs premiers de $F$ sont connus. On suppose que
pour chaque $p\mid F$, un entier $a_p$ comme ci-dessus est donné. Alors 
$N$ est premier.
\end{coro}
\begin{proof}
Si $d\mid N$, alors $d\equiv 1\pmod{F}$ par le Lemme Chinois.
Donc $d = 1$ ou $d \geq F+1 > \sqrt{N}$. Cette dernière inégalité
implique que $d = N$, puisque $N/d < \sqrt{N}$ doit être $1$.
\end{proof}
\end{frame}

\begin{frame}{Produire un grand nombre premier}
\begin{theo}[Théorème des Nombres Premiers (TNP)]
Quand $x\to+\infty$, on a
$$\pi(x) := \#\set{p \leq x\colon \text{$p$ premier}} \sim \frac{x}{\log x}.$$
On a des bornes effectives:
$$\frac{x}{\log x}\Big(1+\frac{1}{2\log x}\Big)\leq\pi(x)\leq \frac{x}{\log
x}\Big(1+\frac{3}{2\log x}\Big),$$
où l'inégalité de gauche est valide pour $x\geq 59$ et celle de droite pour
tout $x > 1$.
\end{theo}
\end{frame}
\begin{frame}
Le nombre de premiers dans $]N, 2N]$ est
$$\pi(2N) - \pi(N) \sim \frac{N}{\log N}\;.$$
En tirant des entiers uniformément au hasard dans cet intervalle, l'espérance
du nombre de tirage avant de produire un premier est donc $\log N$.
\end{frame}

\begin{frame}{Produire beaucoup de petits premiers}
\begin{algorithm}[H]
\caption{Crible d'Ératosthène}
\begin{algorithmic}[1]
\REQUIRE Un entier $B$.
\ENSURE L'ensemble des premiers $p\leq B$.
\STATE Créer un tableau $A[2] = \dots = A[B] = \texttt{vrai}$.
\FOR{$n=2, \dots , \sqrt{B}$}
  \IF[$n$ est premier] {$A[n] = \texttt{vrai}$}
      \FOR[barrer les multiples de $n$]{$k = 2, \dots, B/n$}
      \STATE $A[kn] \leftarrow \texttt{faux}$, \COMMENT{$kn$ n'est pas premier}
      \ENDFOR
  \ENDIF
\ENDFOR
\STATE Afficher les $n$ tels que $A[n] = \texttt{vrai}$.
\end{algorithmic}
\end{algorithm}
Le nombre d'opérations est 
$$2B + \sum_{p\leq \sqrt{B}} \floor{B/p} = 2B + O(\sqrt{B}) + B\sum_{p\leq
\sqrt{B}} \frac{1}{p} \sim B\log\log B, $$
en utilisant $\sum_{p\leq x} p^{-1}\sim \log\log x$, qui suit par exemple
du TNP et d'une sommation d'Abel.
\end{frame}

\section{Factorisation}

\begin{frame}{Entiers friables}

\begin{defi}
Soit $B> 0$. Un entier $N > 0$ est
\begin{itemize}
\item $B$-friable au sens restreint si ($p$ premier divise $N$) implique
 $p \leq B$;
\item $B$-friable si ($p^k$ divise $N$) implique $p^k \leq B$
(pour tout $p$ premier et tout entier $k$).
\end{itemize}
\end{defi}

\begin{theo}[de Bruijn] Soit
$\psi(x,y) = \#\set{ n \leq x\colon \text{$n$ est $y$-friable} }$.
On choisit $y = x^{1/u}$ et on suppose que $(\log x)^\e  \leq u \leq (\log
x)^{1-\e}$ pour un $0 < \e < 1$, alors
$$\frac{\psi(x,x^{1/u})}{x} = u^{-u + o(u)}$$
quand $x\to \infty$.
\end{theo}
\end{frame}

\begin{frame}
On se permettra le raisonnement \red{non rigoureux}~consistant à supposer
que la proportion d'entiers friables dans certains ensembles est proche des
$u^{-u}$ du théorème. Voici un exemple simple:
\begin{algorithm}[H]
\caption{La méthode $p-1$ de Pollard}
\begin{algorithmic}[1]
\REQUIRE $N$ un entier, $B$ une borne de friabilité.
\ENSURE Un facteur non trivial de $N$ ou \kbd{\red{Échec}}.
\STATE À l'aide du crible d'Ératosthène calculer les premiers $\ell \leq B$.
\STATE Tirer $a\in \ZM/N\ZM$ uniformément au hasard. Soit $b \leftarrow a$.
\FOR[calculer $b = a^{\ppcm(2,\dots,B)}$]{$\ell\leq B$}
\STATE Soit $k$ l'exposant maximal tel que $\ell^k \leq B$.
\STATE $b \leftarrow b^{\ell^k}$.
\ENDFOR
\IF{$d := \gcd(b-1, N)$ est un diviseur non trivial de $N$}
  \STATE Afficher $d$.
\ELSE
  \STATE \kbd{\red{Échec}}.
\ENDIF
\end{algorithmic}
\end{algorithm}
\end{frame}

\begin{frame}
L'algorithme trouve un facteur quand l'ordre de $a$ modulo un
diviseur de $N$ est $B$-friable, ssi l'ordre de $a$ modulo un
diviseur \emph{premier} de $N$ est $B$-friable. Ceci se produit en
particulier si $p-1$ est $B$-friable et a peu de chance de se produire sinon:
\begin{lemme}
Soit $\ell$ est un diviseur premier de $p-1$, un $a\in \FM_p^*$ a un ordre
divisible par $\ell$ dans $\FM_p^*$ avec probabilité $\geq 1 - 1/\ell$.
\end{lemme}
\begin{proof}
Dans un groupe cyclique $\gen{g}$ d'ordre $n$ divisible (exactement)
par $\ell^e$, l'ordre de $g^k$ est $n/\pgcd(n, k)$. Il est
premier à $\ell$ ssi $v_\ell(k) \geq e$, soit $n/\ell^e$ valeurs de $k$. 
La probabilité est donc exactement $1 - 1/\ell^e$.
\end{proof}
En particulier, si $\ell > B$ est un grand diviseur premier de $p-1$,
cette probabilité $\geq 1 - 1/\ell \approx 1$.
\end{frame}

\begin{frame}
Donc à  la fin de la boucle \textbf{for}, $b = a^{\ppcm(2,\dots,B)}$ est
congru à $1$ modulo~$p$ si $p-1$ est $B$-friable. Et donc $p\mid b-1$. Avec
un peu de chance, $N\nmid b-1$ et $d$ est un facteur non trivial.
L'algorithme peut échouer pour 2 raisons:
\begin{itemize}
\item $d = 1$: il n'y a pas de diviseur premier $p\mid N$ tel que
that $p-1$ est $B$-friable. Il faut augmenter $B$ et recommencer.
\item $d = N$: l'ordre de $a\in (\ZM/N\ZM)^*$ est $B$-friable. Ce qui veut
probablement dire que $\phi(N)$ est $B$-friable. Il faut diminuer $B$
et recommencer.
\end{itemize}
\begin{alertblock}{Complexité}
Le coût de la méthode est dominé par le calcul de $b$:
$$ \sum_{\ell^k \leq B} (\log \ell^k) O(\log N)^2 = O(B (\log N)^2). $$
\end{alertblock}
\end{frame}
\end{document}

Assuming that $p-1$ is $B$-powersmooth is a little extreme. We increase our
chances by assuming it is $B_1$-powersmooth, up to a single prime less than
$B_2\gg B_1$. There is a nice way of implementing this idea, based on the fact
that primes are relatively plentiful, and the differences $p_{i+1} - p_i$
between consecutive primes are rather small. (To be taken with a grain of salt:
it is an easy exercise to show that $\limsup_i p_{i+1} - p_i = +\infty$; the
``converse'' statement $\liminf_i p_{i+1} - p_i = 2$ is the famous \emph{Twin
primes conjecture}.)

\begin{algorithm}[H]
\caption{Pollard's $p-1$ method, with $B_2$ phase}
\begin{algorithmic}[1]
\REQUIRE $N$ an integer, $(B_1, B_2)$ smoothness bounds.
\ENSURE A non-trivial factor of $N$ or \kbd{Fail}.
\STATE Pick a random $a\in\ZM/N\ZM$ and compute $b = a^{\ppcm(2,\dots,B_1)}$
as in the standard method.
\STATE Let $S = \set{b^{p_{i+1} - p_i}}$, where the $p_i$, $1\leq i\leq K$ are
the consecutive primes $B_1 < p \leq B_2$. This is a (small) set indexed by
the $p_{i+1}-p_i$.

\STATE Set $b \leftarrow b^p_1$;
\FOR{$i = 1,\dots, K - 1$}
  \STATE If $d = \gcd(b-1, N)$ is a non-trivial divisor of $N$, return $d$.
  \STATE Replace $b\leftarrow b \times S[p_{i+1}-p_i]$.
  \COMMENT{$b = a^{\lcm(2,\dots B_1) p_{i+1}}$}
\ENDFOR
\STATE Return \kbd{Fail}.
\end{algorithmic}
\end{algorithm}
\noindent In effect, instead of a powering cost of
$\sum_{p < B_2} \log p \sim B_2$ multiplications, we have $\pi(B_2)\sim
B_2/\log B_2$ multiplications. If $B_2$ is so large that a full fledged
sieving of $[0,B_2]$ becomes impractical, we can precompute the primes up to
$\sqrt{B_2}$ and sieve out smaller slices $[kM, (k+1)M]$ with 
$k = \floor{B_2/M}$.
\smallskip

The $p-1$ method has the very nice feature of being sensitive to the size of
the smallest prime divisor of $N$: smaller numbers are smoother. On the other
hand the first point above is a big problem: either there exists a prime
divisor $p$ with $p-1$ smooth, or there does not and we are lost. The elliptic
curve method nowadays completely supersedes $p-1$: it will try \emph{many}
orders $\#E(\F_p)$ instead of the single $\#\F_p^* = p-1$, by varying the curve
$E$. All these orders have roughly the same size as $p-1$, hence supposedly
the same chance of being smooth, using the heuristic principle discussed
above.
\scribe{13}{---}
\def\L{\Lambda}
\def\O{\mathcal{O}}

\section{Primality proving \& factoring with elliptic curves}
\subsection{Elliptic curves over $\ZM/N\ZM$}
Let $N > 0$ be an integer coprime to $6$. An ``elliptic curve'' over $\ZM/N\ZM$
is a Weierstrass equation
$$ E\colon Y^2Z = X^3 + aXZ^2 + bZ^3,\quad a,b\in\ZM/N\ZM,\quad
  4a^3 + 27b^2 \in(\ZM/N\ZM)^*.$$
This defines a ``nonsingular curve'' in the projective space $\P^2(\ZM/N\ZM)$:
$$ \set{(x,y,z)\in (\ZM/N\ZM)^3, \gcd(x,y,z,N) = 1}/
\text{multiplication by $\lambda\in(\ZM/N\ZM)^*$}.$$
The class of $(x,y,z)$ in $\P^2(\ZM/N\ZM)$ is denoted $(x:y:z)$ as usual. If
$p\mid N$, there is a natural projection $\pi:\P^2(\ZM/N\ZM) \to \P^2(\ZM/p\ZM)$
inducing a natural map from $E$ to $E_p$, the curve over $\ZM/p\ZM$ defined by
reducing the equation of $E$ modulo $p$, i.e.~we can reduce $P\in E(\ZM/N\ZM)$
to $\pi(P)\in E_p(\ZM/p\ZM)$. Basic facts about elliptic curves can be found in
Silverman~\cite{Sil:ell}.
\begin{theo} If $N$ is prime
\begin{enumerate}
\item $E(\ZM/N\ZM)$ has a natural structure of commutative group. The group
law is denoted $(P,Q)\mapsto P+Q$ with neutral element $O_E = (0:1:0)$. It
is given by polynomial mappings (depending on the coefficients of $E$)
in the coordinates of $P$ and $Q$, formally the same ones as in the ``chord
and tangent process'' over $\R$ or $\Q$.

\item $E(\ZM/N\ZM)$ has at most two cyclic components.

\item $(\sqrt{N}-1)^2 < \#E(\ZM/N\ZM) < (\sqrt{N}+1)^2$ (Hasse's bound).
\end{enumerate}
\end{theo}
Now a non-theorem: if $N$ is not prime, $E(\ZM/N\ZM)$ is definitely not
a group. But we may still try to add points applying the same defining
formulae as if $N$ were prime. The worse obstruction we may encounter is a
non-invertible $d\in (\ZM/N\ZM)\setminus\set{0}$. In this case, $\gcd(d,N)$ is
a non-trivial factor of $N$. In the text, we now assume that all computation
depicted in curves over $\ZM/N\ZM$ (e.g.~compute $P+Q$) do succeed. Whenever
they do not we obtain a non-trivial factor of $N$, which is usually our main
motivation.

More generally, we define $[m]P$ for $m\in\ZM$ and $P\in E(\ZM/N\ZM)$ by
$$[0]P := O_E,\quad [m] P := [m-1]P + P,~\text{for $m > 0$}$$
and $[m]P := [-m]P$ for $m < 0$. If $N$ is prime, we have genuine associative
group law and $[m]P = P + \dots + P$ with $m$ summands, for $m > 0$;
otherwise, the result is undefined if one of the addition fails.
The only result we will need about this pseudo group law is that if $p\mid N$
is a prime, $\pi:\P^2(\ZM/N\ZM) \to \P^2(\ZM/p\ZM)$ is the natural projection,
and $P,Q\in E(\ZM/N\ZM)$ such that $P + Q$ is well-defined, then
$$\pi(P + Q) = \pi(P) + \pi(Q),\quad\text{and}\quad \pi([m]P) = [m]\pi(P), $$
where the right-hand side additions use the ordinary group law on $E_p(\ZM/p\ZM)$.

We will subsequently use freely operations in $E(\ZM/N\ZM)$, with the
convention that any such operation failing provides a non trivial factor of
$N$ and aborts all computations.

\subsection{The basic idea (Goldwasser-Killian)}
We now adapt Pocklington's theorem \ref{th:pock}, in the simplest setting,
not meant to be practical.
\begin{theo} Let $N$ be an integer coprime to $6$, let $E$ be an elliptic
curve over $\ZM/N\ZM$, $P\in E(\ZM/N\ZM)$, and $m > 0$ an integer such that
\begin{itemize}
\item There exists a prime divisor $q$ of $m$ with $q \geq (N^{1/4}+1)^2$,

\item $[m] P = O_E$, but $[m/q] P = (x:y:z)$, with $(z,N) = 1$.
\end{itemize}
Then $N$ is prime.
\end{theo}

\begin{proof} Assume $N$ is composite, and let $p \leq N^{1/2}$ be the
smallest prime divisor of $N$. The order $r$ of $\pi(P)\in E_p(\ZM/p\ZM)$
divides $m$ but not $m/q$, hence $q\mid r$. On the other hand, by Hasse's
bound,
$$ r\leq \#E_p(\ZM/p\ZM) < (p^{1/2}+1)^2 \leq (N^{1/4}+1)^2, $$
hence $q < (N^{1/4}+1)^2$, a contradiction.
\end{proof}
If $N$ is prime the above just uses a curve $E$ and $P\in E(\ZM/N\ZM)$ of
provably large order (divisible by $q$). It is natural to choose
$m = \#E(\ZM/N\ZM)$ and try random points on the curve:
\begin{prop} Let $N > 3$ be prime, $E$ an elliptic curve
over $\ZM/N\ZM$, $m = \#E(\ZM/N\ZM)$, and $q$ a prime factor of $m$.
Then a random point $P\in E(\ZM/N\ZM)$ satisfies $[m/q] P = O_E$ with
probability $1/q$.
\end{prop}
\begin{proof}
Since $m < (\sqrt{N}+1)^2$, we have $v_q(m) = 1$. The requested property is
true for any abelian group $G$ satisfying $v_q(\#G) = 1$. Indeed, we may
write $G = \ZM/q\ZM \oplus H$ for some abelian group $H$ or order $h$ (coprime
to $q$); the condition $h (a\oplus b) = 0$ is equivalent to $a = 0$, which is
true for a fraction $h/\#G = 1/q$ of all elements of $G$.
\end{proof}
\begin{algorithm}[H]
\caption{Goldwasser-Killian primality test}
\begin{algorithmic}[1]
\REQUIRE $N > 1$, coprime to $6$.
\ENSURE A primality proof for $N$.
\STATE Pick $a,b\in \ZM/N\ZM$ at random and let $E:Y^2Z = X^3 + aXZ^2 + bZ^3$.
\STATE Compute $m = \#E(\ZM/N\ZM)$, as if $N$ were prime.
\STATE Try to factor $m$: if it factors completely leaving a factor $q\geq
(N^{1/4}+1)^2$ which looks prime (fails a few compositeness tests).
\STATE Recursively prove the primality of $q$. If it fails, start over at (1).
\STATE Find $P\in E(\ZM/N\ZM)$ such that $[m/q]P = (x:y:z)$, with
$\gcd(z,N) = 1$ and $[m]P = O_E$.
\COMMENT{pick a random $x\in\ZM/N\ZM$ until $x^3+ax+b$ is a square, then let
$y$ be a square root and set $P = (x:y:1)$.}
\end{algorithmic}
\end{algorithm}
In the above we factor the quadratic polynomial $Y^2 - (x^3 + ax + b)$ as if
$N$ were prime: if it fails, $N$ is composite. We can simplify the last step
by picking simultaneously $E$ and $P$: pick randomly $x,y,a\in\ZM/N\ZM$ and set
$b = y^2 - x^3 - ax$.

The big problem with the algorithm is that $m$ is difficult to compute.
Goldwasser and Killian use Schoof's algorithm which runs in time $O(\log
N)^8$, assuming $N$ is prime. Even with a lot of improvements since (in
particular by Elkies and Atkin), this is still impractical to prove the
primality of large integers, say 10000 digits. Atkin's idea is to consider
curves with complex multiplication, so that $m$ is known in advance from a
simple formula.

\subsection{Introduction to complex multiplication}
An elliptic curve over $\C$ is a torus $\C/\L$, where $\L$ is
a lattice, i.e.~a rank $2$ submodule. In particular, $\L$ is not
contained in $\R$.
\begin{defn}
An \emph{elliptic function} with period lattice $\L$ is a meromorphic
function $f$, such that $f(z+w) = f(z)$ for all $w\in\L$. In other
words it induces a well-defined function on $\C/\L$ with finitely many
poles deleted.
\end{defn}
One of the simplest examples is Weierstrass $\wp$-function:
$$ \wp(z;\L) := \wp(z) = \frac{1}{z^2} +
  \sum_{w\in \L\setminus\set{0}} \paren{\frac{1}{(z-w)^2} - \frac{1}{w^2}}. $$
It satisfies the following differential equation:
$$ \wp'(z)^2 = 4\wp(z)^3 - g_2 \wp(z) - g_3,\quad
\text{where }
g_2 = 60 \sum_{w\in\L\setminus\set{0}} \frac{1}{w^4},
\quad
g_3 = 140\sum_{w\in\L\setminus\set{0}} \frac{1}{w^6}.
$$
(The proof is easy: an elliptic function without poles is constant, because
it is entire and bounded. Apply this to the difference
$4\wp(z)^3 - g_2 \wp(z) - g_3-\wp'(z)^2$.)
Note that $g_2$ and $g_3$ are well-defined, in fact
\begin{lemma} For any lattice $\L \subset \C$, the series
$$\sum_{w\in\L\setminus\set{0}} \frac{1}{\abs{w}^s},$$
converges if $s > 2$.
\end{lemma}
\begin{proof} Prove that $C_k = \#\set{w\in \L, \abs{w} \leq k} = C(\L) k^2 +
O(k)$, for some constant $C(\L)$. It follows that $\#\set{w\in \L, k\leq
\abs{w} < k+1} = O(k)$. Summing by parts, the sum converges for $s > 2$.
\end{proof}


\begin{prop} We have $g_2^3 - 27 g_3^2 \neq 0$, i.e the projective curve
$y^2z = 4x^3 - g_2 xz^2 - g_3z^3$ is non-singular.
\end{prop}
\begin{rem}
The mapping
\begin{eqnarray*}
\C/\L &\to & \P^2(\C)\\
  z & \mapsto & \begin{cases}
    (\wp(z):\wp'(z):1) & \text{if $z\not\in\L$,}\\
    (0:1:0) & \text{if $z\in\L$,}
  \end{cases}
\end{eqnarray*}
is a complex isomorphism between the torus $\C/\L$ and the non-singular
projective curve $E: y^2z = 4x^3 - g_2 xz^2 - g_3 z^3$. This endows $E$
with a natural group structure, which coincides with the chord-and-tangent
law.
\end{rem}
We now consider morphisms between complex elliptic curve, that is
holomorphic, $\ZM$-linear maps:
\begin{theo}
\begin{enumerate}
\item The curves $\C/\L$ and $\C/\L'$ are isomorphic if and only if there
exists $\alpha\in\C^*$, $\L' = \alpha\L$.

\item $\End(\C/\L) = \set{\alpha\in\C \colon \alpha\L = \L}$.

\item $\End(\C/\L) = \ZM$ or an order $\O$ in an imaginary quadratic field
(i.e.~$\O = \ZM + w\ZM$ with $\im(w) > 0$ and $w^2 - sw + d =0$ for some
$s,d\in\ZM$).

\item Let $j(E) = j(\L) = 1728 g_2^3 / (g_2^3 - 27g_3^2)$. This $j$-invariant
characterizes the isomorphism class of $E = \C/\L$: $j(E) = j(E')$ if and only
if $E\cong E'$.

\item $j(\alpha \L) = j(\L)$ for any $\alpha\in\C^*$.
\end{enumerate}
\end{theo}

\begin{coro}\label{co:Ej} It is easy to write a Weierstrass equation for a
complex curve with given $j$-invariant:
\begin{enumerate}
\item If $j = 0$, take $y^2 = x^3 - 1$.
\item If $j = 1728$, take $y^2 = x^3 - x$.
\item If $j \neq 0,1728$, let $c = j/(1728 - j)$ and take
$y^2 = x^3 + 3cx + 2c$. The right hand side has discriminant
$-2^2 3^3 c^2(c+1)\neq 0$.
\end{enumerate}
We denote $E(j)$ the equation given above. The formula is in fact valid over
any base whose characteristic is not $2$ or $3$.
\end{coro}

\begin{defn} $E$ has complex multiplication by $\O$ if $\End(E) = \O$ is
strictly larger than $\ZM$. We say $E$ has CM by $\O$.
\end{defn}
\begin{ex} The curve $\C/\ZM[i]$ has CM by $\ZM[i]$. It is isomorphic
to $E:y^2 = x^3 - x$, which has extra endomorphism $(x,y)\mapsto (-x,iy)$.
\end{ex}

From now on, we insist that a basis $(\w_1,\w_2)$ for $\L$ be positively
oriented: $\im (\w_1/\w_2) > 0$, which is easily achieved by swapping $\w_1$
and $\w_2$.
Since $j(\alpha \L) = j(\L)$, we may assume that $\L = \gen{\tau, 1}_\ZM$,
with $\im \tau > 0$. Given a basis $(\w_1,\w_2)$ such that $\tau = \w_1/\w_2$
has positive imaginary part, we set $j(\tau) := j(\gen{\tau,1}_\ZM)$.
\begin{rem}
The reason for the weird normalizing constant $1728$ for $j$ is to
ensure the following identity
$$ j(\tau) = \frac{1}{z} + 744 + \sum_{n\geq 1} c_n q^n,
  \quad\text{with $q = \exp(2i\pi \tau)$},$$
where the $c_n$ are positive \emph{integers}.
\end{rem}
\def\MM{
  \paren{\begin{smallmatrix}
  a & b\\
  c & d
  \end{smallmatrix}}
}
The fact that $j(\L)$ is a function on lattices, which we compute using any
positively oriented basis is equivalent to saying that $j(\tau)$ is invariant
under the natural action of $\Sl_2(\ZM)$:
$$ \MM \cdot \tau = \frac{a\tau + b}{c\tau + d}. $$
Namely $(\w_1,\w_2)\to
(a\w_1 + b, c\w_2 + d)$, $\MM\in\Gl_2(\ZM)$, gives the general base change and
$$\im\paren{\frac{a\tau +b}{c\tau+d}} =
  \im\paren{
    \frac{ (a\tau + b) \overline{(c\tau+d)} }
         { \abs{c\tau + d}^2 }
  }
  =
    \frac{ (ad-bc)\im\tau }
         { \abs{c\tau + d}^2 } > 0
$$
restricts us to $\Sl_2(\ZM)$. Hence, we may further impose that
$\tau$ belongs to the standard fundamental domain for the action
of $\Sl_2(\ZM)$ on Poincar\'e's half-plane $\im(z) > 0$:
$$ \abs{\re(z)} \leq \frac{1}{2},\quad \abs{z} \geq 1. $$
In particular $\im \tau \geq \sqrt{3}/2$ and
$\abs{q} \leq \exp(-\pi\sqrt{3}) \approx 0.0043$. From this,
$j(\tau)$ is easy to approximate numerically. In fact, we find
$$
g_2 = \frac{1}{12}\paren{\frac{2\pi}{\w_2}}^4 \paren{
  1 + 240 \sum_{n\geq 1} \frac{n^3q^n}{1-q^n}
},
$$
$$
g_3 = \frac{1}{216}\paren{\frac{2\pi}{\w_2}}^6 \paren{
  1 + 504 \sum_{n\geq 1} \frac{n^5q^n}{1-q^n}
}.
$$
This is not the fastest way to compute $j$, but already quite efficient:
$n^5q^n$ tends very quickly to $0$.

\subsection{Some algebraic number theory}
A $z\in\C$ is \emph{algebraic} if it is a root of a non-zero polynomial in
$\ZM[X]$. It is an \emph{algebraic integer} if that polynomial can be chosen
to be \emph{monic}.

\def\A{\mathfrak{A}}
\def\B{\mathfrak{B}}
\def\p{\mathfrak{p}}

A number field $K\subset \C$ of degree $n$ is a finite extension of $\Q$ of
degree $n$, i.e.~a field which is a $\Q$-vector space of finite dimension
$n$. The algebraic integers in $K$ form a ring $\Z_K$. An \emph{integral
ideal} is a non-zero ideal in $\Z_K$, a \emph{fractional ideal} is a subset
$\A$ of $K$ such  that $d\A$ is integral for some $d\in K$. A fractional
ideal, in particular $\Z_K$, is a free $\ZM$-modules of rank~$n$.

\begin{rem} We define number fields as embedded in $\C$. This is not a
necessity, and is in fact the wrong point of view. We could view $K$ as
an abstract field embedding $\Q\subset K$ or, more concretely but less
adequately, as a quotient ring $K = \Q[X]/(T)$, for some irreducible
$T\in\Q[X]$ of degree~$n$ (this follows from the primitive element theorem,
and is not suitable to define extensions over more general bases than $\Q$,
e.g.~$\F_p(t)$).
To each complex root $\a_i$ of $T$ corresponds an embedding $K\to \C$,
sending the class of $X$ to $\a_i$, and each complex embedding is of this
form. In this way, an abstract number field of degree $n$ comes equipped with
$n$ canonical embeddings into the complex numbers, or any algebraically closed
field. There is no reason to favor any of them.

For instance, the field $\Q[X]/(X^3 - 2)$ has three different embeddings,
$\Q(2^{1/3})$, $\Q(2^{1/3}j)$ and $\Q(2^{1/3}j^2)$, which are isomorphic as
fields, but definitely not identical. For one thing, the first one is a
subset of $\R$.
\end{rem}

There is a natural multiplication on the set of integral ideals:
$\A\B$ is the smallest integral ideal containing all $ab$, $a\in\A$,
$b\in\B$. This extends in a natural way to fractional ideals.

\begin{theo}
\begin{enumerate}
\item $\Z_K$ is a Dedekind ring: the fractional ideals of $K$ form an abelian
group under multiplication, with neutral element $\Z_K$. Any fractional ideal
can be written uniquely as a product of maximal ideals:
$\A = \prod \p^{e_\p}$, where all $e_\p$ but finitely many are $0$.
$\A$ is integral, if and only if $e_\p\geq 0$ for all $\p$. If $\p\subset
\Z_K$ is a maximal ideal, then $\Z_K/\p$ is a finite field.

\item If $\A$ is an integral ideal, then the norm of $\A$, $N\A := \Z_K/\A$
is finite, this is a multiplicative map: $N(\A\B) = N\A \cdot N\B$, which
extends to fractional ideals by multiplicativity.

\item Let $I_K$ be the group of fractional ideals, and $P_K$ be the subgroup of
\emph{principal} fractional ideals. The quotient group $I_K/P_K$ is a finite
abelian group $\Cl(K)$, the class group of $K$.

\item There exists a finite Galois extension $H_K/K$, the Hilbert class field
of $K$, whose Galois group is $\Cl(K)$. A maximal ideal $\p\subset \Z_K$
splits completely in $H_K$ if and only if it is principal.
\end{enumerate}
\end{theo}
\noindent (The ideal $\p$ splits completely in $L/K$ if $\p\Z_L$ is a product
of $[L:K]$ distinct maximal ideals in $\Z_L$; they all satisfy
$\Z_L/\mathfrak{P} = \Z_K/\p$.)
\medskip

We shall see in the next lecture how to compute class groups of imaginary
quadratic fields. From this, the $j$-invariant will enable us to compute
Hilbert class fields. There are beautiful and important algorithms for the
general case of arbitrary number fields, and generalizations of the Hilbert
class field, just beyond the scope of our lectures. Class fields provide a
complete solution to the inverse Galois problem for abelian groups. In short,
they describe all abelian extensions of a given number field $K$, in terms of
arithmetic data depending on $K$ only. For an introduction to this so-called
Class Field Theory in a context very close to ours, see
Cox~\cite{Cox:prifor}, then Cohen~\cite{Coh:coucom, Coh:advcom} for a
computational approach.

Let us consider a few examples :
\begin{enumerate}
\item $K = \Q$, one finds $\Z_K = \ZM$, $\Cl(K) = \set{1}$ ($\ZM$ is principal,
in fact Euclidean), hence $H_K = K$.

\item $K = \Q(i)$, one finds $\Z_K = \ZM[i]$, $\Cl(K) =
\set{1}$ ($\ZM[i]$ is again Euclidean), hence $H_K = K$.

\item $K = \Q(\sqrt{-6})$, one finds $\Z_K = \ZM[\sqrt{-6}]$,
$\Cl(K) \simeq \ZM/2\ZM$, generated by the maximal ideal $\p$ generated by
$2$ and $\sqrt{-6}$, which is \emph{not} principal; in this case
$\Z_K/\p = \F_2$. The Hilbert class field $H_K$ is
$$K(\sqrt{-3}) = K(\sqrt{2}) = \Q(\sqrt{2} + \sqrt{-3}).$$
\end{enumerate}
\begin{rem} The notation $\sqrt{d}$ for $d < 0$ denotes the complex number
$i\sqrt{d}\in\C$. Had we taken the better point of view that $K = \Q(\sqrt{d})$
is really $\Q[X]/(X^2 - d)$, for some non-square $d$, we could just say it is
the class of $X$ in $K$.
\end{rem}

\begin{exo} Let $d$ be a squarefree integer, $K = \Q(\sqrt{d})$. Prove that
$\Z_K = \ZM[\w]$, where
$$ \w =
\begin{cases}
  \sqrt{d} & \text{if $d\equiv 2,3\pmod{4}$}, \\
  \displaystyle
  \frac{1 + \sqrt{d}}{2} & \text{if $d\equiv 1\pmod{4}$}.
\end{cases}
$$
(When is $(u + \sqrt{d})/2$ an algebraic integer, if $u,v\in\Q$ ?)
\end{exo}
The \emph{discriminant} of a quadratic field $\Q(\sqrt{d})$, $d$ squarefree,
is $D = 4d$ if $d\equiv 2,3\pmod{4}$, and $d$ otherwise. Then
$\Z_K = \ZM[\frac{D+\sqrt{D}}{2}]$ in all cases.
\scribe{14}{---}

\subsection{Class groups of imaginary quadratic fields}

Let $K = \Q(\sqrt{D})$ be the imaginary quadratic field of discriminant $D < 0$.
The most efficient representation for handle ideal classes in $\Z_K$
uses an isomorphism with classes of integral binary quadratic forms
modulo the action by $\Sl_2(\ZM)$ given by change of variables. We
will stick to ideals, which entails minor inefficiencies.
See~\cite[Chap.5]{Coh:coucom} for details.

The proofs of the following lemmas are not difficult and left as exercises:
\begin{lemma}\label{le:Na}
If $\alpha\in K\subset \C$, then $N(\alpha) = \abs{\alpha}^2$.
\end{lemma}
\begin{lemma}
Let $K$ be a quadratic field of discriminant $D$. All integral ideals in $\Z_K$
are of the form $\A = \delta \big( a\ZM + \frac{-b+\sqrt{D}}{2}\ZM \big)$ for
some $a,\delta\in\Z_{>0}$, $b\in\ZM$, such that $-a < b \leq a$ and $b^2
\equiv D \pmod{4a}$. Conversely, these $\ZM$-modules are \emph{distinct}
ideals ($= \Z_K$-modules). Further, $\A \cap \ZM = \delta a\ZM$ and $N\A =
a\delta^2$.
\end{lemma}
\begin{proof}
Tedious but simple computations. (Write $\Z_K =
\gen{1,\frac{D+\sqrt{D}}{2}}_\ZM$ and $\A$ as a submodule given by an HNF
basis.) Note that the lemma holds for real and imaginary fields.
\end{proof}
\begin{defn}
An integral ideal is \emph{primitive} if it is not of the form $\delta \A$
with $\A$ integral and $\delta > 1$.
We represent the primitive ideal $\big( a\ZM + \frac{-b+\sqrt{D}}{2}\ZM \big)$
by the triple $(a,b,c)\in\ZM^3$, with $a > 0$, $-a < b \leq a$ and
$c := (b^2 - D)/(4a) > 0$. Since $c$ can be deduced from $a$, $b$ and $D$, we
may omit it in the notation, as in $(a,b,*)$.
\end{defn}
The condition $-a < b \leq a$ only says that $b = \MOD{b, 2a}$, and
corresponds to the obvious fact that $\gen{a, \tau}_\ZM = \gen{a, \tau - qa}_\ZM$
for any $q\in\ZM$. Since we are mostly interested in ideal classes, it does not
hurt to assume that ideals are primitive. Note also that if $\tau = aX -
\frac{-b+\sqrt{D}}{2}Y$ lies in the ideal $(a,b,c)$, i.e.~if $X,Y\in\ZM$,
then 
\begin{equation}\label{eq:Norm}
N(\tau) = \abs{\tau}^2 = a(aX^2 + bXY + cY^2)
\end{equation}
(Here come the binary quadratic forms.)
\begin{lemma}\label{le:rho}
With the previous notations, let
$$\A = (a,b,c),\quad
  \B = (c,\MOD{-b, 2c}, *),\quad
  \tau  =  \frac{b+\sqrt{D}}{2a}\in K.$$
Then $\A$ and $\B$ are in the same ideal class. In fact, $\B = (\tau)\A$.
\end{lemma}
\begin{coro}
Each ideal class in $\Z_K$ contains a unique ideal of the form $\A = (a,b,c)$
such that
$$ \abs{b} \leq a \leq c,$$
and $b\geq 0$ if one inequality is an equality. Such an ideal is called
\emph{reduced}.
\end{coro}
\begin{proof}
Existence is easy: pick a representative in the ideal class such that
$a\in\Z_{>0}$ is minimal. Then $a \leq c$ by minimality and the previous
lemma. The other conditions are easy.

We now prove unicity. Using \eqref{eq:Norm}, we claim that
$$a^2 = \min_{x\in\A\setminus\set{0}} \abs{x}^2,\quad
  ac = \min_{x\in\A\setminus\ZM} \abs{x}^2. $$
Let us prove the first one: $a^2$ is obviously attained ($X = 1$, $Y = 0$); 
using the defining equalities $\abs{b}\leq a \leq c$, we have
$$ aX^2 + bXY + cY^2 \geq a(X^2 - \abs{XY} + Y^2) \geq a, $$
since $X,Y\in \ZM$ implies 
$$X^2 - \abs{XY} + Y^2 = (X - \abs{Y}/2)^2 + \frac{3}{4}Y^2 \geq 1,\quad
(X,Y)\in\ZM^2\setminus\set{(0,0)}.$$
The second equality follows analogously, by investigating the consequences of
$Y\neq 0$.

Assume now that $\A = (a,b,c)$ and $\A' = (a',b',c')$ are reduced and in the
same ideal class: $\A = \alpha \A'$ for some $\alpha\in K^*$. This implies
$N\A = N(\alpha)N\A'$ hence $a = \abs{\alpha}^2 a'$ by the multiplicativity of
norms and Lemma~\ref{le:Na}. Then
$$ \set{\abs{x}^2\colon x\in \A'\setminus\set{0}} = \abs{\alpha}^2
   \set{\abs{x'}^2\colon x'\in \A'\setminus\set{0}},
$$
hence they have the same minimum and $a^2 = \abs{\alpha}^2 a'^2$. It follows
that $a = a'$ and $\abs{\alpha} = 1$. Then $\A\cap \ZM = \A'\cap \ZM = a\ZM$ and
$$ \set{\abs{x}^2\colon x\in \A'\setminus\ZM} =
   \set{\abs{x'}^2\colon x'\in \A'\setminus\ZM},
$$
from which we obtain $ac = a'c'$, hence $c = c'$. Since $b^2 - 4ac = b'^2 -
4a'c'$, it follows that $b = \pm b'$. By the convention on the sign of $b$,
we can assume $0 < \abs{b} < a < c$, otherwise $b,b'\geq 0$ and we are done.

In these conditions, the only solutions of $ aX^2 + bXY + cY^2 = a $ are
$(\pm 1, 0)$ (refine the computations above). Since $a\in \A$, there exists
$u = Xa' - Y\frac{-b'+\sqrt{D}}{2}\in \A'$, $X,Y\in\ZM$, such that $a = \alpha
u$, hence $\abs{u}^2 = a^2$, which now implies that $(X,Y)=(\pm1, 0)$.
Finally $\alpha = \pm 1$, and $\A = \A'$.
\end{proof}
Note that $\Z_K$ is always reduced and is represented either by $(1,0,-D/4)$
or by $(1,1,(1-D)/4)$ depending on $D\bmod 4$. More importantly, the triples
representing reduced ideals are easily bounded: in fact, let $\Delta =
\abs{D} = -D$, the definitions $\abs{b}\leq a\leq c$ and $D = b^2 - 4ac$
imply
$$ -D = 4ac - b^2 \geq 4a^2 - a^2 = 3a^2, $$
hence $a \leq \sqrt{\Delta/3}$. This yields a simple algorithm to enumerate
$\Cl(K)$:
\begin{algorithm}[H]
\caption{Class group of imaginary quadratic fields}
\begin{algorithmic}[1]
\REQUIRE $D < 0$, discriminant of a quadratic fields $K$; we let $\Delta = -D$.
\ENSURE A set of reduced ideal representatives of $\Cl(K)$.
\FOR{$a = 1,\dots, \sqrt{\Delta/3}$}
  \FOR{$b = 0,\dots, a$ such that $b \equiv \Delta \pmod{2}$}
  \STATE Let $c = (b^2 + \Delta)/4a$. 
  \IF{$c\in\ZM$ and $a \leq c$}
   \STATE Print $(a,b,c)$.
   \STATE If $b\neq a\neq c$ and $b\neq 0$, print $(a,-b,c)$.
  \ENDIF
  \ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}
\begin{theo}
This algorithm prints all reduced ideals in $\Z_K$ in time $\Ot(D)$.
\end{theo}
\begin{proof}
The two outer loops have length $O(\sqrt{\Delta})$.
\end{proof}
One proves that $\#\Cl(D) \ll \sqrt{\Delta}\log \Delta$, hence the algorithm
above is certainly not optimal. In fact the Brauer-Siegel theorem states that
$\log \#\Cl(D) \sim \log(\sqrt{\Delta})$ as $D$ tends to infinity, so the
size of the output is indeed roughly $\sqrt{\Delta}$. It is possible to
enumerate $\Cl(D)$ in time essentially linear in the size of the output by
describing first $\Cl(D)$ in terms of generators and relations,
see~\S\ref{se:clgp}. Note that the error terms in Brauer-Sieger are
\emph{ineffective} unless we assume a Riemann Hypothesis.

\begin{algorithm}[H]
\caption{Reduction of ideals in imaginary quadratic fields}
\begin{algorithmic}[1]
\REQUIRE A primitive integral ideal $\A = (a,b,c)$ in $\Z_K$.
\ENSURE The reduced representative $\B$ of the ideal class of $\A$, and
a $\tau\in K^*$ such that $\B = \tau \A$.
\STATE Set $\tau \leftarrow 1$.
\WHILE{$a > c$ or ($b < 0$ and $a = c$) }
\STATE Let $a' = c$, $b' = \MOD{b, 2a'}$, $c' = (b'^2 - D)/(4a') $.
\STATE Set $(a,b,c)\leftarrow (a',b',c')$.
\STATE Set $\tau \leftarrow \tau \times \frac{b+\sqrt{D}}{2a}$.
\ENDWHILE
\end{algorithmic}
\end{algorithm}
\begin{proof}
Since we assume $-a < b\leq a$, it is impossible that $b = -a$ and the output
is correct by repeated application of Lemma~\ref{le:rho}. The only thing to
prove is that the algorithm stops. If $a = c$ and $b < 0$ at the beginning of
the loop then $(a,b,a)$ is replaced by $(a,-b,a)$ and we exit the loop in the
next iteration. Otherwise, $a\in\Z_{>0}$ decreases strictly from one loop to
the next, and we are done. With a little care~\cite[Prop~5.4.3]{Coh:coucom},
one proves $a' \leq a/2$ except in the very last iteration, so there are
$O(\log a)$ iterations.
\end{proof}

\begin{algorithm}[H]
\caption{Solving $U^2 - D V^2 = 4N$}
\begin{algorithmic}[1]
\REQUIRE $D < 0$ discriminant of a quadratic field; $N$ an odd
prime coprime to $D$.
\ENSURE Return a solution $(U,V)$ of $U^2 - D V^2 = 4N$,
  or \kbd{False} if none exist.
\STATE Factor the quadratic polynomial $X^2 - D$ in $\ZM/N\ZM$, as if $N$
were prime.
\STATE If the polynomial is irreducible, return \kbd{False}.

\STATE Let $0 < b < N$ be a square root of $D$ modulo $N$. If $b$ and $D$ have
different parities, set $b \leftarrow N - b$.

\COMMENT{Now, $b^2 \equiv D \pmod{4N}$.}
\STATE Let $c = \frac{b^2 - D}{4N}\in \ZM$. Using the previous reduction
algorithm with input $\A = (N, b, c)$, find a reduced representative $\B =
(a,*,*)$ of $\A$, and $\tau\in K$ such that $\B = \tau \A$.
\STATE If $a\neq 1$, return \kbd{False}.
\STATE Write $1/\tau = \frac{U+V\sqrt{D}}{2}$ and return $(U,V)$.
\end{algorithmic}
\end{algorithm}
\begin{proof}
The equation means $N = \alpha \overline{\alpha}$, where $\alpha =
(U+V\sqrt{D})/2$ is an algebraic integer, since it is a root of the monic
$X^2 - U X + N\in \ZM[X]$. The integral ideal $(\alpha)$ has norm $N$, which
is prime, hence it must be primitive and can be represented as $(N,b,*)$
where $b^2 \equiv D\pmod{4N}$. Provided this is possible, the equation has a
solution if and only if this ideal is principal, i.e.~$\B = \Z_K$, which is
the same as $a = 1$.
\end{proof}
The proof shows that, if $\alpha = (U + V\sqrt{D})/2$ is the
solution returned for the equation $\text{Norm} \alpha = N$, the others are
of the form $\zeta \alpha$ or $\zeta \bar{\alpha}$, where $\zeta \in \Z_K^*$.
Hence there are either $0$ or exactly $2w(D)$ solutions, where $w(D) =
\#\Z_K^*$ is the number of units in $\Z_K$, i.e.~ $w(D) = 2$ for $D < -4$,
$w(-4) = 4$, $w(-3) = 6$.

\subsection{ECPP}
Let $K = \Q(\sqrt{D})$ be an \emph{imaginary} quadratic field of
discriminant $D< 0$. If $\A\subset \Z_K \subset \C$ is an integral
ideal, $\C/\A$ is an elliptic curve with CM by $\Z_K$.

\begin{theo}
\begin{enumerate}
\item The Weierstrass equation $E$ of $\C/\A$ is defined over $H_K$, in
particular $j(E) = j(\A)\in H_K$. Note that $j(\A)$ only depends on the class
of $\A$ in $\Cl(K)$. In fact, if $\A$ runs through the classes of $\Cl(K)$,
the $j(\A)$ define the $\C$-isomorphism classes of elliptic curves with CM by
$\Z_K$.

\item Let $$\Phi(X) = \prod_{\A\in\Cl(K)} \big(X - j(\A)\big).$$
Then $\Phi(X)\in \ZM[X]$ is irreducible and any root of $\Phi$ generates $H_K/K$.

\item\label{eq:splitN} A prime $N$ splits completely in $H_K/\Q$ if and only
if the equation $U^2 - D V^2 = 4N$ has a solution in integers $U,V$. In this
case, maximal ideals $\p$ above $N$ in $H_K$ satisfy $\Z_K/\p = \ZM/N\ZM$ and
are principal. 
\end{enumerate}
\end{theo}
\begin{exo} Using the algorithm in the previous lecture, show that $K =
\Q(\sqrt{-163})$ has trivial class group. Then explain 
why $\exp(\pi\sqrt{163})$ is very close to an integer.
\end{exo}

For a root $j\in H_K$ of the modular polynomial $\Phi(X)$, let $E(j)$ the
complex curve of Corollary~\ref{co:Ej}, which is defined over $H_K$. In the
situation of $(\ref{eq:splitN})$, $N$ splits completely and we can
intuitively reduce the equation $E$ modulo $\p$, to obtain $\bar{E}$ over
$\ZM/N\ZM$. Unfortunately, even though $j$ is integral, the equation $E(j)$
does not have integral coefficients, and denominators are a nuisance. The
proper way to proceed is as follows: $\Phi(X)$ splits into distinct linear
factors modulo $N$ and its roots $\bar{j}$ are the reductions of the $j$
invariants of the $\C$-isomorphism classes of curves with CM by $\Z_K$. The
whole point of the construction, besides surprisingly producing explicit
curves $\bar{E} = E(\bar{j})$ over $\ZM/N\ZM$ from complex analytic data, is
that the $\#\bar{E}(\ZM/N\ZM)$ are known:
\begin{theo}
\begin{enumerate}
\item In the above situation, $\#\bar{E}(\ZM/N\ZM) = N+1 - U$ for some solution
$(U,V)$ of $U^2 - D V^2 = 4N$.  Note that Hasse's bound $\abs{U} < 2\sqrt{N}$
is obvious in this case.

\item Conversely, there are $w(D)$ such solutions $U$, where $w(D) =
\#\Z_K^*$, and each give rise to the cardinality of a curve
\end{enumerate}
\end{theo}
We can now formulate roughly the main ideas in Atkin's algorithm. Its
complexity is not rigorously analyzed, but optimized variants are the fastest
known methods in practice.
\begin{algorithm}[H]
\caption{ECPP primality test}
\begin{algorithmic}[1]
\REQUIRE $N$ an integer
\ENSURE \kbd{True} if $N$ is prime, \kbd{False} otherwise.
\FOR[Loop over imaginary quadratic fields $K = \Q(\sqrt{D})$] 
    {$D = -3,-4,-7,\dots$ }
  \IF{$D$ is a discriminant and $4N = U^2 - D V^2$ has integer solutions}
  \STATE Compute $m_U = N+1 - U$ for all solutions $(U,V)$. If one of these
  is completely factored up to a large probable prime $q \geq (N^{1/4}+1)^2$. 
  \ENDIF
\ENDFOR
\STATE Compute representatives $\A$ for the elements of $\Cl(K)$.
\STATE Compute floating point approximations of the $j(\A)$, then of the
polynomial $\Phi(X)$ and round its coefficients to the nearest integer.

\COMMENT{If $N$ is prime, then $\Phi$ splits in $\ZM/N\ZM$}
\STATE Compute a root $\bar{j}$ of $\Phi$ in $\ZM/N\ZM$, and write a Weierstrass
equation for $\bar{E}$ with $j$-invariant $\bar{j}$.

\STATE Test a few random points $P$ until we believe that $\#\bar{E}(\ZM/N\ZM)
 = m_U$, i.e.~we always have $[m_U] P = O_E$. If for even a single $P$,
the test fails, replace $E$ by its quadratic twist. (If $D = -3, -4$,
consider all quadratic twists until we find one whose cardinality
is probably $m_U$.)

\STATE Use the Goldwasser-Killian test to prove that $N$ is prime,
assuming that $q$ is: pick a random point $P$ and check that $[m_U/q] P =
(x:y:z)$,  with $\gcd(z,N) = 1$.

\STATE Then recursively prove the primality of $q$.
\end{algorithmic}
\end{algorithm}
The algorithm is not completely formalized and it is clear there are many
places where it can be improved. For instance,
\begin{itemize}
\item One should consider the $D$ by increasing class numbers. Also, better
invariants than $j$ are known (smaller polynomials than $\Phi$) to compute
$H_K/K$.
\item With some more theoretical effort, one can avoid almost all the
guesswork when matching $m_U$ to a specific curve (not up to quadratic twist
as shown above).
\item A heuristic analysis shows that the most time consuming part
is the solving of $b^2 \equiv D\pmod{N}$, so we can restrict the $D$ to be
products of small primes $p_i$ and precompute their square roots. Then the
square root of $D$ can be recovered by a multiplication. This is the main
idea in the FastECPP algorithm, which is conjectured to run in randomized
time $\Ot(\log N)^4$, where the original algorithm was conjectured to run in
randomized times $\Ot(\log N)^5$. Current records for primality proofs of
general integers use FastECPP and lie around 40000 decimal digits
(February 2020).
\end{itemize}
As in \S\ref{se:certificate}, ECPP produces a primality certificate for $N$, of
the form $C(N)$, which consists in
\begin{itemize}
\item the integer $N$,
\item a curve $E$ over $\ZM/N\ZM$ and a point $P\in E(\ZM/N\ZM)$,
\item an integer $m$ divisible by $q \geq (N^{1/4}+1)^2$,
such that $[m]P = O_E$ and $[m/q]P = (x:y:z)$ with $\gcd(z,N) = 1$,
\item a certificate $C(q)$ for $q$.
\end{itemize}

\subsection{Factoring with elliptic curves}
This is straightforward generalization of the $p-1$ method from~\S\ref{se:p-1}.

\begin{algorithm}[H]
\caption{Lenstra's ECM factorization algorithm}
\begin{algorithmic}[1]
\REQUIRE $N$ an integer, $B$ a smoothness bound.
\ENSURE A non-trivial factor of $N$ or \kbd{Fail}.
\STATE Using Eratosthenes's sieve, compute all primes $p \leq B$.
\STATE Pick a random curve $E$ over $\ZM/N\ZM$ and $P\in E(\ZM/N\ZM)$. Let $Q = P$.
\def\tmp{[\lcm(2,\dots,B)]}
\FOR[compute $Q = \tmp P$]{$p\leq B$}
\STATE Let $k$ be maximal such that $p^k \leq B$.
\STATE Set $Q := [p^k]Q$. If during the computation we hit a point 
$R=(x:y:z)$ with $z\neq 0$ but $d = \gcd(z,N) > 1$, the computation is
impossible, but we are happy and return the factor $d$\,!
\ENDFOR
\STATE Return \kbd{Fail}.
\end{algorithmic}
\end{algorithm}
\noindent Just as for the $p-1$ method, we can introduce a $B_2$-phase
to cater for $\#E(\F_p)$ which are $B_1$-powersmooth up to a single
larger prime $\leq B_2$.
\begin{guess}
With suitable parameters, ECM runs in randomized time
$L_{1/2}(p)^{1/\sqrt{2} + o(1)}$, where $p$ is the smallest prime
divisor of $N$. Since $p\leq \sqrt{N}$, this is $L_{1/2}(N)^{1 + o(1)}$.
\end{guess}
\scribe{15}{---}

\section{Factoring and sieving algorithms}
\subsection{The basic idea} We want to find $x,y\in\ZM$ such that
$$x^2\equiv y^2\pmod{N},\quad x\not\equiv \pm y \pmod{N}.$$
Since this is impossible if $(\ZM/N\ZM)^*$ is cyclic (unless we stumble directly
on $x,y$ not belonging to $(\ZM/N\ZM)^*$, which is highly implausible but would
indeed yield factors), we must
check that $N$ is an not a prime power before embarking on this course of
action. We may as well require that it is not a pure power, of the form $N =
q^k$. Note that $k = O(\log N)$ and an approximation to $N^{1/k}$ is easily
computed for each given $k$ using Newton's method (or approximating
$\exp(\frac{1}{k}\log N)$), so this is not a costly pre-condition :

\def\B{\mathcal{B}}
\begin{algorithm}[H]
\caption{Generic factorization algorithm}
\begin{algorithmic}[1]
\REQUIRE An odd integer $N$, not a pure power.
\ENSURE A non-trivial factor of $N$ or \kbd{Fail}.
\STATE Choose a factorbase $\B$, e.g. $\set{-1}\cup \set{p \leq B\colon
\text{$p$ prime}}$.
If some $p\leq B$ divides $N$, return~$p$.
\STATE Produce many congruences (relations) of the form 
$$ x_j^2 \equiv \prod_{i\in\B} i^{e_{i,j}} \pmod{N}, \quad j \leq J, $$
where $e_{i,j}\in\ZM$, but may as well be taken in $\set{0,1}$.

\STATE If $v = (v_j)$ is a non-zero vector in the kernel of $(e_{i,j})$,
viewed as a matrix over~$\F_2$, then $\sum_j e_{i,j} v_j \equiv 0\pmod{2}$
for all $i\in \B$ and
$$ \paren{\prod_j x_j^{v_j}}^2 \equiv
   \paren{\prod_{i\in \B} i^{ \frac{1}{2}\sum_j e_{i,j}v_j} }^2 \pmod{N}, $$
which is of the required form $x^2 \equiv y^2 \pmod{N}$.
\STATE If $x\equiv \pm y\pmod{N}$, return \kbd{Fail}.
\end{algorithmic}
\end{algorithm}
Of course, in practice, we do not return \kbd{Fail}, but compute further
kernel vectors. The number of square roots of $1$ in $\ZM/N\ZM$ is $2^\omega$,
where $\omega$ is the number of distinct prime divisors of $N$. So two random
$(x,y)$ such that $x^2\equiv y^2\pmod{N}$ yield a trivial factor with
probability $2^{1-\omega} \leq 1/2$ provided $\omega \geq 2$. We now must
make the second step more precise.

\subsection{Finding relations: Dixon's random squares}
The whole difficulty is now to find relations, and then to choose suitably the
factorbase depending of our relation-finding algorithm.
The simplest idea (Dixon's random squares) is to pick $t\in [1,N]$ at
random. If $\MOD{t^2, N}$ factors on $\B$, we have found a relation. Of
course, we want $t\approx B$ to that $\MOD{t^2, N}$ be of the order of
$\sqrt{N}$ and no larger. This method provably runs in expected time
$L_{1/2}(N)^{O(1)}$.
\begin{lemma} Let $N$ be an odd integer. Let $p_1,\dots,p_h$ be the
  consecutive prime numbers, $r\in\N$ such that $p_h^{2r} \leq N$ and suppose
  that $(N,p_1\dots p_h) = 1$. Let
  $$ S := \set{1\leq b < N\colon \text{$\MOD{b^2, N}$ is $p_h$-smooth}}. $$
  Then $ \#S \cdot (2r)! \geq h^{2r} $.
\end{lemma}
\begin{proof} Let $N = \prod_{i\leq \omega} q_i^{\ell_i}$ be the prime
  factorization of $N$. For each $i$, let $\chi_i:(\ZM/q_i^{\ell_i})^\times\to
  \set{-1,1}$ be the quadratic characters and
\begin{align*}
  \chi\colon (\ZM/N\ZM)^\times & \longrightarrow G:=\set{-1,1}^\omega \\
a & \longmapsto (\chi_1(a),\dots,\chi_\omega(a)).
\end{align*}
We let $Q := ((\ZM/N\ZM)^\times)^2$ be the set of invertible squares; by the
Chinese remainder theorem, $a\in Q \Leftrightarrow \chi(a) = 1$. For $x\in\R$
and $s\in\N$, we let
$$T_s(x) := \set{a\leq x\colon \exists e_1,\dots,e_h\in\N, a = p_1^{e_1}\dots
  p_h^{e_h}, e_1+\dots+e_h = s}$$
be the set of $p_h$-smooth integers with $s$ prime factors. We partition
$T_s(\sqrt{N})$ into $2^\omega$ sets $U_g$, $g\in G = \set{-1,1}^\omega$, according to
the values of the quadratic character $\chi$:
$$ U_g := \set{a\in T_r(\sqrt{N}) \colon \chi(a) = g }.$$
Finally, we let $V$ be the image of the multiplication map $\cup_g U_g\times
U_g \to \N$: obviously $V \subset Q\cap T_{2r}(N)$.

Every element in $Q \cap T_{2r}(N)$ has exactly $2^\omega = \#G$ square roots,
all belonging to $S$, hence $\#S \geq \#G \cdot \#\big(T_{2r}(N)\cap Q\big)
\geq \#G \cdot \#V$.

Now, $\binom{2r}{r}\#V \geq \#\paren{\cup_{g\in G} U_g \times U_g} = \sum_g
(\# U_g)^2$, since
there at most $\binom{2r}{r}$ ways to split a given $a\in T_{2r}(N)$
into a product of two elements of $T_r{\sqrt{N}}$. By Cauchy-Schwarz,
$$\#G \sum_{g\in G} (\# U_g)^2 \geq \Big(\sum_{g\in G} \# U_g\Big)^2 =
\paren{ \# T_r(\sqrt{N})}^2.$$

Since $p_h^r \leq \sqrt N$, we have
$$\#T_r(\sqrt N) = \#\set{(e_i)\in \N^r
\colon e_1+\dots+e_h = r} = \binom{h+r-1}{r} \geq h^r / r!,$$
and we are done.
\end{proof}
We can now bound the expected number of trials before finding a single
$B$-smooth integer among the $\MOD{x_i^2, N}$,
where the $x_j$ are chosen independently, uniformly at random in $[1,N]$ :
$$ \frac{N}{\#S} \leq \frac{N \cdot (2r)!}{h^{2r}}. $$
Let $n := \ln N$; assuming Dixon's algorithm eventually tests the smoothness
of $k$ integers before producing $h + 2$ relations, it uses the following
numbers of bit operations:
\begin{itemize}
  \item $\Ot(h)$ to produce the first $h$ primes,
  \item $k\, O(\M(n)))$ to compute the $\MOD{x_j^2,N}$,
  \item $k\, O((h+n)\M(n))$ for smoothness tests: a nonsmooth number costs
    $O(h\M(n))$ ($h$ divisions fail), a smooth number costs $O((h+n)\M(n))$:
    in the worst case $h-1$ divisions fail, and the $O(n)$ (not necessarily
    distinct) primes dividing this smooth integer $< N$ are found using that
    many divisions.
  \item $O(h^3)$ to solve the linear system over $\F_2$,
  \item $O(h \M(n))$ to compute $x$,
  \item $O(h (h + \log h \M(n)))$ to compute $y$.
\end{itemize}
For a total cost of $\Ot(h^3 + k(h+n)\M(n))$. We choose $B = N^{1/(2r)}$,
hence $\ln B = n/2r$;
by the prime number theorem $h = \pi(B) \sim B/\ln B$. The expected number $k$
of trials is less than
$$\frac{N \cdot (2r)!}{h^{2r}} \sim (\ln B)^{2r} (2r)! < n^{2r}. $$
Using $h < B$, the total cost is dominated by $(B^3 + n^{2r+2}B)$; this
is minimal when both summands are equal,~i.e. $n^{r+1} = B$, hence
$(r+1)\ln n = \ln B = n/(2r)$. Since $n\to\infty$, $r$ tends to $\infty$
as well and $r\sim r+1$, thus a natural choice is
$r = \ceil{\sqrt{\frac{n}{2\ln n}}}$.
Then $\ln B \leq \sqrt{\frac{n\ln n}{2}}$.
\begin{theo} Dixon's random squares algorithm uses an expected number of
  $\Ot\paren{L_{1/2}(N)^{3/\sqrt{2}}}$ bit operations.
\end{theo}

In practice, it is preferable to choose $x_i$ not much larger than $C :=
\floor{\sqrt{N}}$; indeed if $t = C + a$, for $a=1, 2, \dots$ not too large,
then
$$\MOD{t^2, N} = \paren{C + a}^2 - N,$$ 
is of the order of $\sqrt{N}$, hence more likely to be smooth than a random
integer $< N$. This is the basic idea behind the quadratic sieve. 

\subsection{Finding relations: the quadratic sieve}

It is quite costly to check directly that a given integer is $B$-smooth: about
$B/\log B$ divisions. Sieves are slower, but they can check a whole range of
numbers simultaneously, at an essentially constant cost per number. Just like
Eratosthenes's sieve produces many more primes than a single primality proof.
The main problem with the trial division approach is that almost all numbers
tested are not smooth, so we have a huge amount of wasted work.

Let $Q(X) = (X + C)^2 - N$, with $C = \floor{\sqrt{N}}$. Since this is a
polynomial in $\ZM[X]$, if $m \mid Q(a)$, then $m\mid Q(a + \lambda m)$ for all
$\lambda\in\ZM$.

\begin{algorithm}[H]
\caption{Quadratic sieve}
\begin{algorithmic}[1]
\REQUIRE An integer $N$, a factorbase $\B$, a sieving bound $M > 1$. We assume
that all $p\in \B$ satisfy $\leg{N}{p} = 1$.
\ENSURE A set of $a \leq M$ such that $Q(a)$ is $\B$-smooth: $p\mid Q(a)$
implies $p\in \B$.
\STATE Build an array $A[a] = Q(a)$, for $1 \leq a \leq M$.
\STATE If $2\in\B$, replace $A[a]$ by its largest odd factor for all $a\leq M$.
\FOR{$p \in \B$ odd prime}
 \STATE Find the largest $k$ such that $p^k \leq Q(M)$.
 \STATE Find $a_k,b_k$ such that $Q(a_k),Q(b_k) \equiv 0 \pmod{p^k}$.
 \COMMENT{Two solutions mod $p$ then Hensel lift.}
 \FOR{$i = k,k-1,\dots,1$}
  \STATE If $i < k$, set $(a_i,b_i) \leftarrow (a_{i+1},b_{i+1})$ mod $p^i$.
   \FOR{$\lambda\leq M/p^i$, $p\nmid \lambda$}
   \STATE Divide $A[a_i+\lambda p^i]$ by $p^i$ in place.\COMMENT{exact division}
   \STATE Divide $A[b_i+\lambda p^i]$ by $p^i$ in place.\COMMENT{exact division}
  \ENDFOR
 \ENDFOR
\ENDFOR
\STATE Return all the $a$ such that $A[a] = 1$.
\end{algorithmic}
\end{algorithm}
\begin{proof}
The reason for the condition $\leg{N}{p}$ is that $p$ cannot divide $Q(a)$
unless $N$ is a square modulo $p$. Of course, if $p\mid N$, we have
factored~$N$. So the assumption is harmless. Since we ensure $p\neq 2$, it
follows that the equation $x^2 \equiv N \pmod{p^k}$ has exactly
2 solutions for all $k$. The result is correct since we divide the $A[a]$
by primes belonging to $\B$. Note that we may miss some smooth numbers this
way, but this agrees with the specifications.
\end{proof}
Provided $M$ is large enough, the sieve proper dominates the running time.
In an actual implementation, two basic improvements are useful:
\begin{itemize}
\item Initialize $A[a]$ by a rough approximation to $\log Q(a)$, then
subtract approximations to $i\log p$ instead of dividing by $p^i$:
subtractions are cheaper than divisions. Of course, the $\log p$ are
precomputed.

\item Do not sieve by small primes, which cost a lot (there are lots of them)
and do not decrease much the size of $A[a]$. Then we may as well not sieve by
prime powers, since most integers will not be divisible by too many squares
of a not-so-small primes.
\end{itemize}
In the end, we check directly by trial division the $a$ such that $A[a]$ is
not too large. Due to the above two approximations, we may miss quite a few
smooth numbers, which seems wasteful. But we still expect a large number of
the corresponding $Q(a)$ to be smooth. Since the sieve is now much faster,
proper tuning results in a net gain: finding twice fewer relations in each
sieving range is not a major problem if we find them three times faster!

\subsection{The Multiple Polynomials Quadratic Sieve (MPQS)}
Our polynomial $Q$ is nice but it stands all alone, and the $Q(a)$ increase
relatively fast with $a$. We now replace the polynomial $(X + B)^2 - N$
with a more general polynomial $Q(X) = AX^2 + 2BX + C$, with reduced
discriminant $B^2 - AC = N$, hence $AQ(X) = (AX + B)^2 - N$.

What are suitable parameters ? $Q(X)$ is minimal at $-B/A$, with value $-N/A$,
which is fine compared to our old $(X + B)^2 - N$ if $A$ is not much smaller
than $\sqrt{N}$. We can get a symmetric range of small values: for all
$x\in[-B/A-M, -B/A+M]$, we have
$$ -N = AQ(-B/A) \leq AQ(x)\leq AQ(-B/A+M) = (AM)^2 - N,$$
so if $ A \leq \sqrt{2N}/M $, we have
$\abs{Q(x)} \leq N/A \approx M\sqrt{N/2}$.
\begin{algorithm}[H]
\caption{Recipe to find $Q$ for the quadratic sieve}
\begin{algorithmic}[1]
\REQUIRE An odd integer $N$, a sieving bound $M > 1$.
\ENSURE
\STATE Find $A$ odd prime such that $A\approx \sqrt{2N}/M$ and $\leg{N}{A} = 1$.
\STATE Find $B$, $B^2 \equiv N \pmod{A}$ and let $C := (B^2 - N)/A$
\STATE Return $Q = AX^2 + BX + C$.
\end{algorithmic}
\end{algorithm}
\noindent We take $A$ prime and $\leg{N}{A} = 1$ so that the congruence be
solvable (factor a quadratic polynomial over a finite field). Such $A$ are
found by trial and error, trying consecutive integers larger than $\sqrt{2N}/M$
until they fail a few compositeness tests and the Legendre symbol has the
right value. Now when the $Q(a)$ become large, we can find a new polynomial $Q$
with different arithmetic properties, and still relatively small values!

We must also compute the roots of $Q$ modulo primes in the factorbase.
Provided $p\nmid A$, the roots of $Q(a) \equiv 0 \pmod{p}$ are the
$(-B+a_1)A^{-1}\pmod{p}$, $(-B+b_1)A^{-1}\pmod{p}$, with $a_1$, $b_1$ the
square roots of $N \pmod{p}$ as before. If $p\mid A$ there is a single root
$-BC^{-1}$ modulo $p$. Note that it is more difficult to sieve modulo prime
powers when $p\mid A$: another reason to avoid it.

\subsection{The Self Initializing MPQS, Large Prime variations}

It is unfortunately rather costly to change $Q$, so we cannot change it as
often as we please. A very simple idea takes care of the problem, reminiscent
of FastECPP: we do not need $A$ to be prime, only that $B^2 \equiv N\pmod{A}$
be easy to solve. We consider $A = \prod p_i \approx \sqrt{2N}/M$ for some
distinct small primes $p_i$ such that $\leg{N}{p_i} = 1$, with precomputed
squares root $B_i^2 \equiv N \pmod{p_i}$. Then we recover $B$ by Chinese
remaindering.

A final very important practical improvement are the Large Prime variations
(Single, Double, etc.), reminiscent of the $B_2$ phase in $p-1$ and ECM.
We now maintain a database of relations which are smooth, but for a single
Large Prime (or up to \emph{a few} large primes). If we hit another relation
which is almost smooth but for the \emph{same} large primes, we can combine
them and get new relations; or at least get relations involving fewer large
primes. Due to the birthday paradox, we expect to find quite a few new
relations this way. This idea can be used in all the sieving factorization
algorithms.

In practice, the Single and Double large prime variations are easy to
implement, but the combinatorics and the costs of handling the associated
graphs become quickly horrendous as we allow more of them.

\subsection{The Number Field Sieve}
