From: cohen@megrez.ceremab.u-bordeaux.fr (Henri Cohen)
Newsgroups: sci.math
Subject: Re: zeta functions of schemes
Date: 18 Jan 1995 11:30:32 GMT

In article <3fgm1s$ms@matrix.fwi.uva.nl>, mdekker@fwi.uva.nl (Martijn
Dekker) writes:
|> Hi,
|> 
|> just for fun I am writing a program that calculates (approximates)
|> the zeta function of a curve in projective 3-space, defined over
|> a finite field Fp.
|> To do this one needs to count points on the curve C. First count
|> all points with coordinates in Fp, call this number N_1, then
|> count the points with coordinates in Fp^2, call this number
|> N_2 etc. Now the zeta function of C is defined as
|> 
|>  Z(t) = exp(N_1 * t + (N_2)/2 * t^2 + (N_3)/3 * t^3 + ... )
|> 
|> Of course, to count points on Fp^i one needs a representation
|> of this field. I use Fp^i = Fp[X]/f, where f is an irreducible
|> polynomial in Fp[X] of degree i.
|> 
|> The problem is: how to find such an f. Of course I could use symbolic
|> packages (such as Maple, Mathematica or Reduce) to do this, but I like 
|> to do some real programming and I have written it in C.


Let A be a polynomial of degree n. To check whether A is irreducible,
perform the following computations (all done mod p):

1) Compute X^(p^n) modulo A by the binary powering algorithm, reducing
modulo A at each step so you never deal with polynomials of degree
higher than 2n (and all coefficients modulo p). Then check that
the result is equal to X modulo A. If it is not, A is reducible.
2) For every PRIME divisor q of n, compute B=X^(p^(n/q)) modulo A as
in 1). Then using the Euclidean algorithm in F_p, compute the GCD
of B-X with A. If it is not constant for some prime q dividing n,
then A is reducible. If the GCD is constant for every q, then
A is irreducible.

	Hope this helps.

(Of course a number of savings can be trivially done to improve the
algorithm above).