p-adic cohomology and the computation of zeta functions Kiran S. Kedlaya University of California, Berkeley

Elliptic Curve Cryptography Workshop September 24, 2002

See Journal of the Ramanujan Mathematical Society 16 (2001), 323–338 (or arxiv preprint math.AG/0105031).

Zeta functions and cryptography

For C an algebraic curve over a finite field 𝔽_{q}, the 𝔽_{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 zeta function of C:

ζ_{C}(t) = \frac{Q(t)}{(1 − t)(1 − qt)}

by the formula

#J(𝔽_{q}) = Q(1).

Here P is a polynomial over ℤ, which we want to compute.

More on the zeta function

In the formula

ζ_{C}(t) = \frac{Q(t)}{(1 − t)(1 − qt)} ,

Q has integer coefficients. If g = genus of C, then

Q(t) = (1 − tα_{1}) ⋯ (1 − tα_{2g})

for some algebraic integers α_{i} with α_{i}α_{i+g} = q and |α_{i}| = √q. (This constrains the coefficients of Q(t) to lie in some interval.) Moreover,

#C(𝔽_{q^{n}}) = q^{n} + 1 − α_{1}^{n} − ⋯ − α_{2g}^{n}.

Thus Q(t) is determined by #C(𝔽_{q^{n}}) for n = 1, …, g, or even by these counts modulo a suitably large integer N.

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(𝔽_{q}) modulo many small primes.)

In small characteristic (q = p^{n} for p a small prime), methods of Satoh, Fouquet, Gaudry, Harley, Skjernaa, Mestre, etc., work better. (Roughly, compute #C(𝔽_{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).

A general approach in small characteristic

Say q = p^{n}. Write ℚ_{q} for the unramified extension of ℚ_{p} with residue field 𝔽_{q} and ℤ_{q} for its ring of integers.

A construction of Monsky and Washnitzer associates to C a ℚ_{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.

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 𝔽_{q}, where q = p^{n} for p an odd prime. I.e., C is hyperelliptic of genus g with a rational Weierstrass point.

The Monsky-Washnitzer cohomology of C

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.)

This is the “weak completion” of the coordinate ring of the affine variety

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

(Note: S/pS ≅ R/pR.)

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, i.e. f_{x} dx+f_{y} dy, 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 − 1)
H_{+} : \frac{x^{i} dx}{y^{2}} (i = 0, …, 2g).

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. 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(𝔽_{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 ↦ x^{p}.

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

#C(𝔽_{q^{r}}) − #Z(𝔽_{q^{r}}) = #Y (𝔽_{q^{r}})

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

Let π : C → ℙ^{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

#C(𝔽_{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.

Warning: F_{p} is not linear on H, but rather σlinear:

F_{p}(cω) = c^{σ}F_{p}(ω).

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.

In H_{−}, we have the relation

0 ≡ d(C(x)y^{−2s+1} )

≡ C′(x)y^{−2s+1} dx + C(x)(−2s + 1)y^{−2s} dy.

Since P′(x) dx ≡ 2y dy, we get

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

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} dx/y. 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 “roll down” the highest powers of y, eventually obtaining 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.)

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

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+ϵ} ).

Generalizations and variations

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

• Computing a Frobenius lift;

• Finding an efficient reduction procedure for differentials;

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.

The End

23