Next: Example: Computing the Matrix Up: An Example: Computing Previous: An Example: Computing   Contents

## Introduction

Let be the elliptic curve over , given in Weierstrass form, and suppose is a prime of good ordinary6.3 reduction. Kedlaya's algorithm6.4 [Ked01], [Ked04] employs Monsky-Washnitzer cohomology of the affine curve 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 -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 denote the affine curve over cut out by the equation . Consider zeros of , and let

denote the coordinate ring of over . Recall that the hyperelliptic involution

gives us an automorphism of the curves and . This, in turn, induces automorphisms of algebraic de Rham cohomology and , decomposing them into eigenspaces on which acts as the identity and , respectively. In particular,

The -vector space is spanned by the classes of differentials

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

The de Rham complex of is given by

We denote the cohomology groups of this complex by , and as before, they are -vector spaces split into eigenspaces by the hyperelliptic involution. Perhaps more important is that passing from to does not change the presentation of cohomology, and thus we work with and its basis and .

We compute the action of Frobenius on by computing its action on the basis elements. Begin by letting

We have that

as an element of , with a precision of digits. The constant determines the number of digits of precision of the -adic height to be computed (i.e., modulo ), and is the smallest integer such that

As the two differentials and span , we must now be able to write an arbitrary element in (where as a linear combination of , , and . 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 in , the highest monomial of is the one with smallest power of and largest power of .

Example 6.2.2   Let . Then the highest monomial of

is if and if .

Here we outline the reduction algorithm. Begin by computing a list of differentials , where and . Group the terms in as , where have degree less than or equal to 3.

If has a term with , consider the term where is maximal. Take the unique linear combination of the such that when this linear combination is subtracted off of , the resulting  '' no longer has terms of the form . Repeat this process until (or, in more precise terms, the resulting  '' at each step minus linear combinations of differentials) has no terms with .

If has terms with , let be the term with the highest monomial of . Let be the term such that has highest term and subtract off the appropriate multiple of such that the resulting no longer has terms of the form with . Repeat this process until the resulting is of the form .

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

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

Next: Example: Computing the Matrix Up: An Example: Computing Previous: An Example: Computing   Contents
William Stein 2006-10-20