COUNTING POINTS ON CURVES OVER FINITE-FIELDS

We consider the problem of counting the number of points on a plane cu rve, defined by a homogeneous polynomial F(x,y,z) is an element of F-q [x,y,z], which are rational over a ground field F-q. More precisely, w e show that if we are given a projective plane curve C of degree n, an d if C has only ordinary multiple points, then one can compute the num ber of F-q-rational points on C in randomized time (log q)(Delta) wher e Delta = n(O(1)). Since our algorithm actually computes the character istic polynomial of the Frobenius endomorphism on the Jacobian of C, i t follows that we may also compute (1) the number of F-q-rational poin ts on the smooth projective model of C, (2) the number of F-q-rational points on the Jacobian of C, and (3) the number of F(q)m-rational poi nts on C in any given finite extension F(q)m of the ground field, each in a similar time bound. (C) 1998 Academic Press Limited.