Fast computation of a rational point of a variety over a finite field
Open Access
- 20 July 2006
- journal article
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 75 (256) , 2049-2085
Abstract
We exhibit a probabilistic algorithm which computes a rational point of an absolutely irreducible variety over a finite field defined by a reduced regular sequence. Its time-space complexity is roughly quadratic in the logarithm of the cardinality of the field and a geometric invariant of the input system. This invariant, called the degree, is bounded by the Bézout number of the system. Our algorithm works for fields of any characteristic, but requires the cardinality of the field to be greater than a quantity which is roughly the fourth power of the degree of the input variety.Keywords
All Related Versions
This publication has 53 references indexed in Scilit:
- Improved explicit estimates on the number of solutions of equations over a finite fieldFinite Fields and Their Applications, 2006
- The Hardness of Polynomial Equation SolvingFoundations of Computational Mathematics, 2003
- Quadratic Newton Iteration for Systems with MultiplicityFoundations of Computational Mathematics, 2002
- Extended Hilbert Irreducibility and Its ApplicationsJournal of Algorithms, 2000
- Lower bounds for diophantine approximationsJournal of Pure and Applied Algebra, 1997
- Counting curves and their projectionscomputational complexity, 1996
- Effective Noether Irreducibility Forms and ApplicationsJournal of Computer and System Sciences, 1995
- On the efficiency of effective Nullstellens tzecomputational complexity, 1993
- Definability and fast quantifier elimination in algebraically closed fieldsTheoretical Computer Science, 1983
- A lower bound for the number of solutions of equations over finite fieldsJournal of Number Theory, 1974