Counting points on curves over finite fields

We consider the problem of counting the number of points on a plane curve, 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, we show that if we are given a projective plane curve C of degree n, and if C has only ordinary multiple points, then one can compute the number of F-q-rational points on C in randomized time (log q)(Delta) where Delta = n(O(1)). Since our algorithm actually computes the characteristic polynomial of the Frobenius endomorphism on the Jacobian of C, it follows that we may also compute (1) the number of F-q-rational points 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 points 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.