Introduction

Let $E$ be the elliptic curve $y^2 = Q(x)$ over $\mathbb{Z}_p$ , given in Weierstrass form, and suppose $p\geq 5$ is a prime of good ordinary^6.3 reduction. Kedlaya's algorithm^6.4 [Ked01], [Ked04] employs Monsky-Washnitzer cohomology of the affine curve $E\setminus\mathcal{O}$ to compute the zeta function of its reduction over finite fields. While the computation of zeta functions for elliptic curves is best done with algorithms that take into account the group structure, we note that Kedlaya's algorithm was formulated in the more general context of hyperelliptic curves and is of great interest for curves of genus greater than 1. However, more pertinent to our situation is the fact that Kedlaya's algorithm allows us to compute the matrix of absolute Frobenius on Monsky-Washnitzer cohomology, and it is this matrix that allows for fast high-precision computation of $p$ -adic heights using the recent algorithm of Mazur, Stein, and Tate [MST06].

We focus on the computation of this matrix. Details omitted here can be found in the aforementioned papers.

Let $C_{\overline{Q}}$ denote the affine curve over $\mathbb{F}_p$ cut out by the equation $y^2=\overline{Q}(x)$ . Consider $C'_Q = C_Q \setminus \{$ zeros of $y\}$ , and let

$$A = \mathbb{Q}_p[x,y,z]/(y^2-Q(x),yz-1)$$

denote the coordinate ring of $C'_Q$ over $\mathbb{Q}_p$ . Recall that the hyperelliptic involution

$$\iota: (a,b) \mapsto (a,-b)$$

gives us an automorphism of the curves $C_Q$ and $C'_Q$ . This, in turn, induces automorphisms $\iota^*$ of algebraic de Rham cohomology $H^1(C'_Q)$ and $H^1(C_Q)$ , decomposing them into eigenspaces on which $\iota^*$ acts as the identity and $-1$ , respectively. In particular,

$$H^1(C'_Q)=H^1(C'_Q)^+ \oplus H^1(C'_Q)^-.$$

The $\mathbb{Q}_p$ -vector space $H^1(C'_Q)^-$ is spanned by the classes of differentials

$$\left\{[z dx],[xz dx]\right\}.$$

However, the underlying coordinate ring $A$ does not admit the proper lift of Frobenius. To remedy this, we replace $A$ by the dagger ring

$$A^{\dagger} = \left\{\sum_{i,j}a_{i,j}x^iy^j : a_{i,j}\in\mathbb{... ..._{\vert j\vert\rightarrow \infty}\frac{v_p(a_{i,j})}{\vert j\vert} > 0\right\}.$$

The de Rham complex of $A^{\dagger}$ is given by

$$d:A^{\dagger} \longrightarrow A^{\dagger}\frac{z dx}{2},$$

$$\sum_{i,j}a_{i,j}x^iz^j \mapsto\sum_{i,j}a_{i,j}d(x^iz^j)$$

$$=\sum_{i,j}a_{i,j}(2ix^{i-1}z^{j-1}-jx^iQ'z^{j+1})\frac{z dx}{2}.$$

We denote the cohomology groups of this complex by $H^i_{\textrm{MW}}(C'_Q)$ , and as before, they are $\mathbb{Q}_p$ -vector spaces split into eigenspaces by the hyperelliptic involution. Perhaps more important is that passing from $A$ to $A^{\dagger}$ does not change the presentation of cohomology, and thus we work with $H^1_{\textrm{MW}}(C'_Q)^-$ and its basis $z dx$ and $xz dx$ .

We compute the action of Frobenius on $H^1_{\textrm{MW}}(C'_Q)^-$ by computing its action on the basis elements. Begin by letting

$$G(x) = \frac{{\mathrm{Frob}}_p(Q(x))-(Q(x))^p}{p}.$$

We have that

$$F_{p,i}:={\mathrm{Frob}}_p\left(x^iz dx\right) = \sum_{0 \leq k < M}\left(\binom{-1/2}{k} p^{k+1}G^k x^{p(i+1)-1}z^{(2k+1)p-1}\right)zdx,$$

as an element of $\mathbb{Z}_p[x,y,z]/(y^2-Q(x),yz-1)$ , with a precision of $N$ digits. The constant $N$ determines the number of digits of precision of the $p$ -adic height to be computed (i.e., modulo $p^N$ ), and $M$ is the smallest integer such that

$$M-\lfloor\log_p(2M+1)\rfloor\geq N.$$

As the two differentials $z dx$ and $xz dx$ span $H^1_{\textrm{MW}}(C'_{Q})^-$ , we must now be able to write an arbitrary element in $(A^-)^{\dagger}\frac{z dx}{2}$ (where $A^- =\bigoplus_{0 \leq i <3, j \equiv 1(2)}\mathbb{Q}_p x^i y^j)$ as a linear combination of $d(x^iz^j)$ , $z dx$ , and $xz dx$ . With this in mind, we employ a reduction algorithm. For the purposes of this reduction, the following definition is helpful:

Definition 6.2.1   Given a multivariate polynomial $f(x,y,z)$ in $\mathbb{Z}_p[x,y,z]/(y^2-Q(x),yz-1)$ , the highest monomial of $f$ is the one with smallest power of $z$ and largest power of $x$ .

Example 6.2.2   Let $Q(x) = x^3 - x + \frac{1}{4}$ . Then the highest monomial of

$$d(x^iz^j) = 2ix^{i-1}z^{j-1}-3jx^{i+2}z^{j+1}-jx^iz^{j+1}$$

is $x^{i-1}z^{j-1}$ if $1 \leq i < 3$ and $x^2z^{j+1}$ if $i = 0$ .

Here we outline the reduction algorithm. Begin by computing a list of differentials $d(x^iz^j)$ , where $0 \leq i <3$ and $j \equiv 1 \pmod 2$ . Group the terms in ${\mathrm{Frob}}_p(x^iz dx)$ as $(\sum c_{i,j}z^j)zdx$ , where $c_{i,j} \in \mathbb{Z}_p[x]$ have degree less than or equal to 3.

If $F_{p,i}$ has a term $(x^iz^j)zdx$ with $j >0$ , consider the term $(c_{i,j}z^j)zdx$ where $j$ is maximal. Take the unique linear combination of the $d(x^kz^{j-1})$ such that when this linear combination is subtracted off of $F_{p,i}$ , the resulting ``$F_{p,i}$ '' no longer has terms of the form $(x^mz^j)zdx$ . Repeat this process until $F_{p,i}$ (or, in more precise terms, the resulting ``$F_{p,i}$ '' at each step minus linear combinations of differentials) has no terms $(x^mz^j)zdx$ with $j >0$ .

If $F_{p,i}$ has terms with $j \leq 0$ , let $(x^mz^j)zdx$ be the term with the highest monomial of $F_{p,i}$ . Let $(x^kz^l)zdx$ be the term such that $d(x^kz^l)$ has highest term $(x^mz^j)zdx$ and subtract off the appropriate multiple of $d(x^kz^l)$ such that the resulting $F_{p,i}$ no longer has terms of the form $(x^mz^j)zdx$ with $j \neq 0$ . Repeat this process until the resulting $F_{p,i}$ is of the form $\left(a_{0i}+a_{1i}x\right) zdx$ .

Finally, we can read off the entries of the matrix $F$ of absolute Frobenius:

$$F = \left(\begin{array}{cc} a_{00} & a_{01} \\ a_{10} & a_{11} \end{array}\right).$$

Problem 6.2.3   Implement a highly optimized version of the reduction algorithm in SAGE for elliptic curves.