Counting Points on Curves over Finite Fields

AbstractWe consider the problem of counting the number of points on a plane curve, defined by a homogeneous polynomialF(x,y,z) ∈Fq[x,y,z], which are rational over a ground field Fq. More precisely, we show that if we are given a projective plane curve C of degreen, and if C has only ordinary multiple points, then one can compute the number of Fq-rational points on C in randomized time (logq)Δwhere Δ=nO(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 Fq-rational points on the smooth projective model of C, (2) the number of Fq-rational points on the Jacobian of C, and (3) the number of Fqm-rational points on C in any given finite extension Fqmof the ground field, each in a similar time bound