Computing components and projections of curves over finite fields (Q4229409)

The authors present algorithms to compute approximations to the size of curves over finite fields, and to the number of points on one of the coordinate axis with projection fibre on the curve of the same cardinality. The authors refer to this problem as the ``Computational Weil estimate''. The approach is based on the ``Strip-counting'' method introduced in [\textit{J. von zur Gathen, M. Karpinski} and \textit{I. E. Shparlinski}, Comput. Complexity 6, 64-99 (1997)], that uses the principle that the behaviour of the curve can be deduced from its behaviour over a wide enough vertical strip. The idea in this paper is that, for some properties, the strip can be taken small. Related papers to the problem are: \textit{R. J. Schoof}, Math. Comput. 44, 483-494 (1985; Zbl 0579.14025) and \textit{M. D. Huang} and \textit{Y. C. Wong}, Solving systems of polynomial congruences modulo a large prime. Proc. 1996 IEEE Symp. on Foundations of Computer Science, 115-124 (1996).