Counting Points on Curves over Finite Fields. - Huang, Ming-Deh (Journal of symbolic computation.)
We consider the problem of counting the number of points on a plane curve, defined by a homogeneous polynomialF(x,y,z) set membership, variant Image q[x,y,z], which are rational over a ground field Image q. More precisely, we show that if we are given a projective plane curve Image of degreen, and if Image has only ordinary multiple points, then one can compute the number of Image q-rational points on Image in randomized time (logq)Δwhere Δ = nO(1). Since our algorithm actually computes the characteristic polynomial of the Frobenius endomorphism on the Jacobian of Image , it ,follows that we may also compute (1) the number of Image q-rational points on the smooth projective model of Image , (2) the number of Image q-rational points on the Jacobian of Image , and (3) the number of Image qm-rational points on Image in any given finite extension Image qmof the ground field, each in a similar time bound.