Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology

Kiran S. Kedlaya University of California, Berkeley

Midwest Arithmetical Geometry in Cryptography November 2, 2001

Preprint available at

   http://www.math.berkeley.edu/~kedlaya;

to appear in Journal of the Ramanujan Mathematical Society.

Notation

𝔽_{q} — the finite field of q = p^{n} elements (p odd) ℤ_{q} — the unramified extension of ℤ_{p} with residue field 𝔽_{q} (a/k/a W (𝔽_{q})) ℚ_{q} — the fraction field of ℤ_{q} \overline{P} (x) — a monic polynomial of degree 2g + 1 over 𝔽_{q} with distinct roots over \overline{𝔽_{q}} X : y^{2} = \overline{P} (x) — a hyperelliptic curve of genus g with a rational Weierstrass point

The problem

Problem: find α_{1}, …, α_{2g} ∈ ℂ such that |α_{i}| = √q, α_{i}α_{g+i} = q and

#X(𝔽_{q^{r}}) = q^{rn} + 1 − α_{1}^{r} − ⋯ − α_{2g}^{r},

guaranteed to exist by the Weil Conjectures. Then

# Jac (X)(𝔽_{q^{r}}) = 2g ; ∏ ; i=1 (α_{i}^{r} − 1).

The characteristic polynomial of Frobenius:

Q(t) = _{i}^{∏}(t − α_{i})

has integer coefficients, which are bounded in terms of q and g.

Approaches for g = 1

ℓ-adic approach [Schoof, Atkin, Elkies]: compute #X(𝔽_{q}) modulo enough small primes ℓ to determine Q(t) by the Chinese Remainder Theorem (using division polynomials).

p-adic approach [Satoh]: compute #X(𝔽_{q}) modulo a sufficiently high power of p (using Serre-Tate lift).

The ℓ-adic approach is better for p large, the p-adic for p small.

Trouble in higher genus

ℓ-adic approach [Pila]: requires explicit equations for the Jacobian of the curve, which are extremely cumbersome to write down.

p-adic approach [Satoh]: uses formal groups, again cumbersome to write down.

Both approaches are exponential in the genus.

Our goal: give a p-adic computation that is also polynomial in the genus. (Another approach is due to Lauder and Wan; see also Harley’s talk.)

The strategy

We construct a vector space H (“cohomology”) that obeys a Lefschetz trace formula:

#X(𝔽_{q^{r}}) = q^{r} + 1 − Trace (F^{r}, H)

for some linear map F : H → H (“Frobenius”). Then compute Q(t) (resp., the α_{i}) as the characteristic polynomial (resp., the eigenvalues) of F.

We will use Monsky-Washnitzer cohomology, which will produce vector spaces over ℚ_{q}. This cohomology is defined for any affine variety of characteristic p, so we must “puncture” the curve to use it.

The Monsky-Washnitzer cohomology of X

Choose a monic polynomial P (x) over ℤ_{q} congruent to \overline{P} (x) modulo p. The ring R consists of power series

∞ ; ∑ ; i=0 ∞ ; ∑ ; j=−∞ a_{ij}x^{i}y^{j}

over ℤ_{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.)

Geometrically, this is the “weak completion” of the coordinate ring of the affine variety

V = Spec ℤ_{q}[x, y, y^{−1}]/(y^{2} − P (x)).

(That ring has the same reduction modulo p as R does.)

Overconvergence in detail

The series

∞ ; ∑ ; i=0 x^{p^{i}}

is not p-adically convergent. The series

∞ ; ∑ ; i=0 p^{i}x^{p^{i}}

is convergent, but not overconvergent. The series

∞ ; ∑ ; i=0 p^{i}x^{i}

is overconvergent.

A basis in cohomology

The Monsky-Washnitzer cohomology space H is the set of differentials r dx + s dy for r, s ∈ R[\frac{1}{p}], modulo df and f(2y dy − P′(x) dx) for any f ∈ R[\frac{1}{p}].

This is a vector space over ℚ_{q}, which we can split into plus and minus eigenspaces for the map y ↦ −y of R. The resulting spaces have bases

H_{−} : \frac{x^{i} dx}{y} (i = 0, …, 2g)
H_{+} : \frac{x^{i} dx}{y^{2}} (i = 0, …, 2g − 1).

(We’ll see why later.)

Whither overconvergence?

Had we not imposed the overconvergence condition, then

∞ ; ∑ ; i=0 p^{i}x^{p^{2i}−1} dx

would not be zero in H, because its integral

∞ ; ∑ ; i=0 p^{−i}x^{p^{2i}}

does not converge. In fact, H would be infinite dimensional in this case. A typical example in R is

∞ ; ∑ ; i=1 p^{i}x^{i−1} dx = d ( ∞ ; ∑ ; i=1(p^{i}/i)x^{i}) .

A trace formula

Let F : R → R be any map lifting the q-power Frobenius map x ↦ x^{q} modulo p and commuting with y ↦ −y. The Monsky-Washnitzer theory implies the following Lefschetz trace formula:

#X(𝔽_{q^{r}}) = q^{r} + 1 − Trace (F^{r}, H_{−}).

Our plan: compute such a map, compute the matrix by which F acts on some basis of H_{−} to sufficient p-adic precision, and read off the characteristic polynomial.

To simplify matters, we’ll construct F as the n-th power of a map F_{p} lifting the p-power Frobenius x ↦ x^{p}.

The trace formula in detail

Let Z be the set of Weierstrass points of X and Y = X − Z. Then Y is affine and Y = Spec (R/pR), so Monsky-Washnitzer predicts that

#X(𝔽_{q^{r}}) − #Z(𝔽_{q^{r}}) = #Y (𝔽_{q^{r}})
= q^{r} − Trace (F^{r}, H).

Let π : X → ℙ^{1} be the quotient by y ↦ −y. Then ℙ^{1} − π(Z) is again affine, so

q^{r} + 1 − #Z(𝔽_{q^{r}}) = #(ℙ^{1} − π(Z))(𝔽_{q^{r}})

= q^{r} − Trace (F^{r}, H_{+} ).

Subtracting these two yields the trace formula given above:

#X(𝔽_{q^{r}}) = q^{r} + 1 − Trace (F^{r}, H_{−}).

The Frobenius map

Recall that ℤ_{q} has a canonical map σ lifting the map t ↦ t^{p} modulo p. The “Frobenius” map F_{p} : R → R is given by

x ↦ x^{p}
y ↦ y^{p}(1 + pE)^{1/2}

= y^{p} ∞ ; ∑ ; i=0 \binom{1/2}{i}p^{i}E^{i},

where E = (P (x)^{σ} − 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^{σ} d(x^{p}) = px^{p−1}f^{σ} dx.

In practice, compute F_{p}(y) using a Newton iteration, not the power series.

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, …, 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.

Reduction of differentials, part 1

Given a differential A(x)y^{−2s−1} dx with deg A ≤ 2g, write

A(x) = B(x)P (x) + C(x)P′(x)

deg B ≤ 2g − 1, deg C ≤ 2g.

Since P′(x) dx = 2y dy, we get the relation

\frac{C(x)P′(x) dx}{y^{2s+1}} = \frac{2C(x) dy}{y^{2s}} = \frac{2C′(x) dx}{(2s − 1)y^{2s−1}}

in H_{−}. Thus

\frac{A(x)}{y^{2s+1}} dx = \frac{(2s − 1)B(x) + 2C′(x)}{(2s − 1)y^{2s−1}} dx,

and we have reduced the exponent of y in the denominator.

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} y^{−1} dx. Now use the relation

0 = d(x^{m}y)

= mx^{m−1}y dx + x^{m} dy

= \frac{2mx^{m−1}P (x) + x^{m}P′(x)}{2y} dx

to successively eliminate the highest powers of x. (The coefficient of x^{2g+m} in the numerator is 2m + (2g − 1) ≠ 0.)

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, …, 2g − 1, compute an approximation of

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.

and rewrite it as ∑_{i} A_{i}(x)y^{2i+1} dx where each A_{i} has degree at most 2g.

Step 3: take the finite sum ∑_{i} A_{i}(x)y^{2i+1} dx and use the reduction procedures to obtain an equivalent differential of the form A(x) dx/y with deg A ≤ 2g − 1.

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′ = MM^{σ} ⋯ M^{σ^{n−1}}.

Step 5: compute the characteristic polynomial of M′ to high enough accuracy to determine Q(t) and the α_{i}.

Precision

How accurate is accurate enough?

If deg A ≤ 2g and A has coefficients in ℤ_{q}, the reduction of A(x)y^{2s+1} dx will have coefficients in ℤ_{q} if you multiply it by p^{log_{p} 2|s|+1} .

So computing O(gn) terms of

F_{p}(y^{−1}) = y^{p} ∞ ; ∑ ; i=0 \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.)

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 ℤ_{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^{3}n^{3}) memory.

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+ϵ} ) operations on numbers of size O(gn^{2}). This yields a total time of O(g^{4+ϵ} n^{3+ϵ} ).

For g = 1, this is the same asymptotic as Satoh’s algorithm. It is unclear how the two compare in practice, though.

Generalizations

The Monsky-Washnitzer theory applies to any affine scheme; the main difficulties are:

• Finding an easily computed Frobenius lift;

• Finding an efficient reduction procedure for differentials.

Gaudry and Gurel treat the “superelliptic” case y^{n} = f(x), where n is coprime to p, by a similar approach.

The Lauder-Wan method is more general, but less practical. Can it be combined with this?

The End

23