Computing Components And Projections Of Curves Over Finite Fields

. This paper provides an algorithmic approach to some basic algebraic and combinatorial properties of algebraic curves over finite fields: the number of points on a curve or a projection, its number of absolutely irreducible components, and the property of being "exceptional ". 1. Introduction Let F q be a finite field with q elements, f 2 F q [x; y] a bivariate polynomial of total degree n over F q , and C = ff = 0g = f(u; v) 2 F 2 q : f(u; v) = 0g ` F 2 q the plane curve defined by f over F q . In this paper we present some algorithms to compute approximations to the curve size #C and to the number r i of points with exactly i preimages under the projection to a coordinate axis. Since this task generalizes Weil's estimate of #C, it might be called a "computational Weil estimate". In von zur Gathen et al. (1996) , a "strip-counting" method was introduced. It is based on the general principle that the behaviour of a curve can be deduced from its behaviour over a wide enough ve..