On the computation of rational points of a hypersurface over a finite field

GUILLERMO MATERA; MARIANA PÉREZ; MELINA PRIVITELLI

JOURNAL OF COMPLEXITY

ACADEMIC PRESS INC ELSEVIER SCIENCE

Lugar: Amsterdam; Año: 2017 vol. 41 p. 1 - 34

0885-064X

We analyze a family of algorithms for computing rational points ofhypersurfaces defined over a finite field based on searches on ?vertical strips?,namely searches on parallel lines in a given direction. We consider two basic models of generation of vertical strips: an independent model, where repetitions are allowed, and a nonindependent one, where repetitions areavoided. We determine the asymptotic probability distribution of the numberof searches and show that it decays with an exponential ratio in both models.We also analyze the probability distribution of outputs, using the notion of Shannon entropy, and prove that both models are somewhat close to any ideal equidistributed algorithm.