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