\documentclass{slides}
\usepackage{amssymb, amsmath}

\def\FF{\mathbb{F}}
\def\CC{\mathbb{C}}
\def\PP{\mathbb{P}}
\def\QQ{\mathbb{Q}}
\def\ZZ{\mathbb{Z}}
\def\fp{\frac{1}{p}}
\DeclareMathOperator{\Jac}{Jac}
\DeclareMathOperator{\Spec}{Spec}
\DeclareMathOperator{\Trace}{Trace}

\begin{document}

\begin{slide}
  \begin{center}
\textbf{
    $p$-adic cohomology and the computation of zeta functions}
 \\
\medskip
Kiran S. Kedlaya \\
University of California, Berkeley\\
\bigskip
Elliptic Curve Cryptography Workshop
September 24, 2002
  \end{center}

See \textit{Journal of the Ramanujan Mathematical Society}
\textbf{16} (2001), 323--338 (or arxiv preprint math.AG/0105031).

\end{slide}

\begin{slide}
\centerline{\bf Zeta functions and cryptography}

For $C$ an algebraic curve over a finite field $\FF_q$,
the $\FF_q$-rational points of the Jacobian $J(C)$ form
a group possibly useful for cryptography (e.g.,
for Diffie-Hellman exchange), but only if the order of 
the group is known.

The order is determined by the \emph{zeta function}
of $C$:
\[
\zeta_C(t) = \frac{Q(t)}{(1-t)(1-qt)}
\]
by the formula
\[
\#J(\FF_q) = Q(1).
\]
Here $P$ is a polynomial over $\ZZ$,
which we want to compute.
  
\end{slide}

\begin{slide}
 \centerline{\bf More on the zeta function}
In the formula
\[
\zeta_C(t) = \frac{Q(t)}{(1-t)(1-qt)},
\]
$Q$ has integer coefficients. If $g = $ genus of $C$, then
\[
Q(t) = (1 - t \alpha_1)\cdots(1 - t \alpha_{2g})
\]
for some algebraic integers $\alpha_i$ with
$\alpha_i \alpha_{i+g} = q$ and
$|\alpha_i| = \sqrt{q}$.
(This constrains the coefficients of $Q(t)$ to lie in some
interval.)
Moreover,
\[
\#C(\FF_{q^n}) = q^n + 1 - \alpha_1^{n} - \cdots - \alpha_{2g}^n.
\]
Thus $Q(t)$ is determined by $\#C(\FF_{q^n})$ for $n=1, \dots, g$,
or even by these counts modulo a suitably large integer $N$.
\end{slide}

\begin{slide}
 \centerline{\bf The situation in genus 1}

For $C$ an elliptic (genus 1) curve, the best general algorithm
for computing $Q(t)$ is due to Schoof. (Roughly, compute
$\#C(\FF_q)$ modulo many small primes.)

In \emph{small characteristic} ($q = p^n$ for $p$ a small prime),
methods of Satoh, Fouquet, Gaudry, Harley, Skjernaa, Mestre,
etc., work better.
(Roughly, compute $\#C(\FF_q)$ modulo a large power of $p$.)

But all of these methods are specific to genus 1 (though some
may be pushed to genus 2).

\end{slide}

\begin{slide}
\centerline{\bf A general approach in small characteristic}

Say $q = p^n$. Write $\QQ_q$ for
the unramified extension of $\QQ_p$ with residue field $\FF_q$
and $\ZZ_q$ for its ring of integers.

A construction of Monsky and Washnitzer associates to $C$ a $\QQ_p$-vector
space $V$
(cohomology) and a linear
transformation $F$ (Frobenius)
on $V$ with characteristic polynomial $Q(t)$.
If we can compute (approximately) the matrix of $F$ on a basis of
$V$, we can recover $Q(t)$.

In general, this should lead to a computation whose space and
time are polynomial in $p, n, g$.

\end{slide}

\begin{slide}
\centerline{\bf Example: hyperelliptic curves}

We illustrate the construction for
\[
C: y^2 = \overline{P}(x)
\]
for $\overline{P}(x)$ a monic polynomial of degree $2g+1$
over $\FF_q$, where $q = p^n$ for $p$ an \emph{odd} prime.
I.e., $C$ is hyperelliptic of genus $g$ with
a rational Weierstrass point.

\end{slide}

\begin{slide}
\centerline{\bf The Monsky-Washnitzer cohomology of $C$}

Choose a monic polynomial $P(x)$ over $\ZZ_q$ congruent
to $\overline{P}(x)$ modulo $p$.
The ring $R$ consists of power series
\[
\sum_{i=0}^\infty \sum_{j=-\infty}^\infty a_{ij} x^i y^j
\]
over $\ZZ_q$ such that
$v_p(a_{ij})/(i+|j|)$ is eventually bounded away from 0
(``overconvergence''),
modulo the relation $y^2 = P(x)$. (One can assume $a_{ij}=0$ for $i>2g$.)

This is the ``weak completion'' of the coordinate
ring of the affine variety
\[
S = \Spec \ZZ_q[x,y,y^{-1}]/(y^2 - P(x)).
\]
(Note: $S/pS \cong R/pR$.)
\end{slide}

\begin{slide}
\centerline{\bf Overconvergence in detail}

The series
\[
\sum_{i=0}^\infty x^{p^i}
\]
is not $p$-adically convergent.

The series
\[
\sum_{i=0}^\infty p^i x^{p^i}
\]
is convergent, but not overconvergent. 

The series
\[
\sum_{i=0}^\infty p^i x^i
\]
is overconvergent.
  
\end{slide}

\begin{slide}
\centerline{\bf A basis in cohomology}

The Monsky-Washnitzer cohomology space $H$ is the set of differentials
$r\,dx + s\,dy$ for $r,s \in R[\fp]$, modulo $df$, i.e.
$f_x\,dx + f_y\,dy$, and
$f(2y\,dy - P'(x)\,dx)$ for any $f \in R[\fp]$.

This is a vector space over $\QQ_q$, which we can split into
plus and minus eigenspaces for the map $y \mapsto -y$ of $R$. The resulting
spaces have bases
\begin{align*}
H_-: &\quad \frac{x^i\,dx}{y} \quad(i=0, \dots, 2g-1) \\
H_+: &\quad \frac{x^i\,dx}{y^2} \quad(i=0, \dots, 2g).
\end{align*}
We'll see why later.

\end{slide}

\begin{slide}
  \centerline{\bf Whither overconvergence?}

Had we not imposed the overconvergence condition,
then
\[
\sum_{i=0}^\infty p^i x^{p^{2i}-1}\,dx
\]
would not be zero in $H$, because its integral
\[
\sum_{i=0}^\infty p^{-i} x^{p^{2i}}
\]
 does not converge.
In fact, $H$ would be infinite dimensional in this case.

A typical example in $R$ is
\[
\sum_{i=1}^\infty p^i x^{i-1}\,dx = d\left(
\sum_{i=1}^\infty (p^i/i) x^i \right).
\]

\end{slide}

\begin{slide}
\centerline{\bf A trace formula}

Let $F: R \to R$ be any map lifting the $q$-power Frobenius map
$x \mapsto x^q$ modulo $p$ and commuting with $y \mapsto -y$.
Then $F$ acts on differentials by pullback:
\[
F(df) = d(F(f))
\]
so induces a linear transformation on $H_+$ and $H_-$.

The Monsky-Washnitzer theory yields
the following ``Lefschetz trace formula'':
\[
\#X(\FF_{q^r}) = q^r + 1 - \Trace(F^{r}, H_-).
\]
That is, the characteristic polynomial of $F$ on $H_-$ is
$Q(t)$.

We'll construct an $F$ as the $n$-th power of a map
$F_p$ lifting the $p$-power Frobenius $x \mapsto x^p$.
\end{slide}

\begin{slide}
\centerline{\bf The trace formula in detail}

Let $Z$ be the set of Weierstrass points of $C$ and $Y = C-Z$. Then
$Y$ is affine and $Y = \Spec(R/pR)$, so the MW construction yields
\begin{align*}
\#C(\FF_{q^r}) - \#Z(\FF_{q^r}) &= \#Y(\FF_{q^r}) \\
&= q^r - \Trace(F^r, H).
\end{align*}
Let $\pi: C \to \PP^1$ be the quotient by $y \mapsto -y$. Then
$\PP^1 - \pi(Z)$ is again affine, so
\begin{align*}
q^r+1 - \#Z(\FF_{q^r}) &= \#(\PP^1 - \pi(Z))(\FF_{q^r}) \\
&= q^r - \Trace(F^r, H_+).
\end{align*}
Subtracting these two yields
\[
\#C(\FF_{q^r}) = q^r + 1 - \Trace(F^{r}, H_-).
\]

\end{slide}

\begin{slide}

\centerline{\bf The Frobenius map}

Recall that $\ZZ_q$ has a canonical map $\sigma$ lifting the map
$t \mapsto t^p$ modulo $p$.
The ``Frobenius'' map $F_p: R \to R$ is given by
\begin{align*}
  x &\mapsto x^p \\
  y &\mapsto y^p (1 + pE)^{1/2} \\
&= y^p \sum_{i=0}^\infty \binom{1/2}{i} p^i E^i,
\end{align*}
where $E = (P(x)^\sigma - P(x)^p)/(py^{2p})$. (The valuation of
$\binom{1/2}{i}$ is $O(\log i)$, so this is overconvergent.)
Extend $F_p$ to $H$ by sending $f\,dx$ to $f^\sigma\,d(x^p)
= px^{p-1} f^\sigma\,dx$.

Warning: $F_p$ is not linear on $H$, but rather $\sigma$-linear:
\[
F_p(c\omega) = c^\sigma F_p(\omega).
\]

In practice, compute $F_p(y)$ using a Newton iteration, not the power series.

\end{slide}

\begin{slide}
\centerline{\bf What is the matrix?}

We'd like to compute the matrix by which $F_p$, and by extension
$F = F_p^n$, act
on the basis $x^i\,dx/y$ ($i=0, \dots, 2g-1$) of $H_-$.

To do this, we first apply $F_p$ to each differential, then rewrite
the result as an exact differential (which maps to 0 in $H_-$)
plus a linear combination of basis elements.

So we need a procedure to ``reduce'' an arbitrary differential to
a linear combination of basis elements, plus an exact differential.

\end{slide}

\begin{slide}
  \centerline{\bf Reduction of differentials, part 1}

Given a differential $A(x)y^{-2s-1}\,dx$ with $\deg A \leq 2g$,
write
\begin{gather*}
A(x) = B(x)P(x) + C(x) P'(x) \\
\deg B \leq 2g-1, \qquad
\deg C \leq 2g.
\end{gather*}
In $H_-$, we have the relation
\begin{align*}
0 &\equiv d(C(x) y^{-2s+1}) \\
&\equiv C'(x) y^{-2s+1}\,dx + C(x)(-2s+1)y^{-2s}\,dy.
\end{align*}
Since $P'(x)\,dx \equiv 2y\,dy$, we get
\[
\frac{C(x)P'(x)\,dx}{y^{2s+1}} \equiv \frac{2C(x)\,dy}{y^{2s}}
\equiv \frac{2C'(x)\,dx}{(2s-1)y^{2s-1}}.
\]
Thus
\[
\frac{A(x)}{y^{2s+1}}\,dx \equiv \frac{(2s-1)B(x)+2C'(x)}{(2s-1)y^{2s-1}}\,dx,
\]
and we have reduced the exponent of $y$ in the denominator.
\end{slide}

\begin{slide}
\centerline{\bf Reduction of differentials, part 2}

A similar argument allows one to eliminate large positive powers of $y$.
Namely, given $A(x)y^{2s+1}\,dx$, first rewrite it as
$A(x)P(x)^{s+1}\,dx/y$. Now use the relation
\begin{align*}
0 &\equiv d(x^m y) \\
&\equiv mx^{m-1}y\,dx + x^m\,dy \\
&\equiv \frac{2mx^{m-1}P(x) + x^m P'(x)}{2y}\,dx 
\end{align*}
to successively eliminate the highest powers of $x$. (The coefficient
of $x^{2g+m}$ in the numerator is $2m+(2g+1) \neq 0$.)
  
\end{slide}

\begin{slide}
\centerline{\bf The algorithm (sketch, part 1)}

Step 1: use Newton's iteration to compute $F_p(y^{-1})$ to ``high accuracy''.

Step 2: for $i=0, \dots, 2g-1$, compute an approximation of
\begin{align*}
F_p(x^i\,dx/y) &= F_p(y^{-1}) F_p(x)^i F_p(dx) \\
&=
F_p(y^{-1}) x^{pi} px^{p-1}\,dx.
\end{align*}
and rewrite it as $\sum_i A_i(x)y^{2i+1}\,dx$ where each $A_i$ has degree
at most $2g$.

Step 3: take the finite sum $\sum_i A_i(x) y^{2i+1}\,dx$ and use the reduction
procedures to ``roll down'' the highest powers of $y$,
eventually obtaining an equivalent differential 
of the form $A(x)\,dx/y$ with $\deg A \leq 2g-1$.
\end{slide}

\begin{slide}
\centerline{\bf The algorithm (sketch, part 2)}

Step 4: let $M$ be the matrix with $M_{ij}$ equal to the coefficient of
$x^i\,dx/y$ in the reduction of $F_p(x^j\,dx/y)$. Then the matrix
by which $F = F_p^n$ acts on the basis $x^i\,dx/y$ of $H_-$ is
\[
M' = M M^\sigma \cdots M^{\sigma^{n-1}}.
\]

Step 5: compute the characteristic polynomial of $M'$ to high enough accuracy
to determine $Q(t)$ and the $\alpha_i$.

\end{slide}

\begin{slide}
\centerline{\bf Precision: how accurate is accurate enough?}


If $\deg A \leq 2g$ and $A$ has coefficients in
$\ZZ_q$, the reduction of $A(x)y^{2s+1}\,dx$ will have coefficients
in $\ZZ_q$ if you multiply it by $p^{\log_p 2|s|+1}$.

So computing $O(gn)$ terms of
\[
F_p(y^{-1}) = y^{-p} \sum_{i=0}^\infty \binom{-1/2}{i} p^i E^i
\]
will give the needed
$O(gn)$ places of precision in the final matrix. (And all constants
are explicit.)

Note: computations should be done in \emph{fixed precision}, filling
in garbage high-order bits as needed. They drop out later in the
reduction process.


\end{slide}

\begin{slide}
  \centerline{\bf Asymptotics (for fixed $p$)}

One must carry $O(gn)$ places of precision in all computations in order
to get enough accuracy to uniquely determine the characteristic
polynomial $Q(t)$. Moreover, each place of precision requires $O(n)$ bits,
since we're working in $\ZZ_q$.

The limiting memory constraint is storing the approximation of
$F(x^i\,dx/y)$. It consists of $O(gn)$ terms, each a polynomial of degree $2g$,
each of whose coefficients requires $O(gn^2)$ bits to store. Thus it
requires $O(g^3n^3)$ memory.
\end{slide}

\begin{slide}
  \centerline{\bf Asymptotics (for fixed $p$) continued}

The limiting time constraint is reducing each of these $2g$ approximations.
This requires eliminating $O(gn)$ powers of $y$; each such step
requires $O(g^{1+\epsilon})$
operations on numbers of size $O(gn^2)$. This yields
a total time of $O(g^{4+\epsilon} n^{3+\epsilon})$.

\end{slide}

\begin{slide}
\centerline{\bf Generalizations and variations}

The Monsky-Washnitzer theory applies to any smooth affine scheme; the 
main difficulties are:
\begin{itemize}
\item Computing a Frobenius lift;
\item Finding an efficient reduction procedure for differentials;
\end{itemize}
and to a lesser extent analyzing the precision requirements.

Gaudry and Gurel treat the ``superelliptic''
case $y^n = f(x)$, where $n$ is coprime to $p$.
Denef and Vercauteren treat hyperelliptic
curves in characteristic 2.

Related methods, based on work of Dwork, have been developed by
Lauder and Wan.

\end{slide}

\begin{slide}
  \centerline{\bf The End}

\end{slide}

\end{document}

