On the computation of rational points of a hypersurface over a finite field
Authors:
- Guillermo MateraGMGuillermo Matera
- Mariana PérezMPMariana Pérez
- Melina PrivitelliMPMelina Privitelli
Preprint
Abstract
We design and analyze an algorithm for computing rational points of hypersurfaces defined over a finite field based on searches on "vertical strips", namely searches on parallel lines in a given direction. Our results show that, on average, less than two searches suffice to obtain a rational point. We also analyze the probability distribution of outputs, using the notion of Shannon entropy, and prove that the algorithm is somewhat close to any "ideal" equidistributed algorithm.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- On the value set of small families of polynomials over a finite field, IJournal of Combinatorial Theory, Series A, 2014
- Modern Computer Algebra2013
- Counting Reducible, Powerful, and Relatively Irreducible Multivariate Polynomials over Finite FieldsSIAM Journal on Discrete Mathematics, 2013
- Certified Numerical Homotopy TrackingExperimental Mathematics, 2012
- Fast Linear Homotopy to Find Approximate Zeros of Polynomial SystemsFoundations of Computational Mathematics, 2010
- Tropicalization and irreducibility of generalized Vandermonde determinantsProceedings of the American Mathematical Society, 2009
- Fast computation of a rational point of a variety over a finite fieldMathematics of Computation, 2006
- Realistic analysis of some randomized algorithmsJournal of Computer and System Sciences, 1991
- Counting polynomials with a given number of zeros in a finite fieldLinear and Multilinear Algebra, 1990
- The values of a polynomial over a finite fieldGlasgow Mathematical Journal, 1973