Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5773812 | Journal of Complexity | 2017 | 34 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Analysis
Authors
Guillermo Matera, Mariana Pérez, Melina Privitelli,