Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Fast computation of a rational point of a variety over a finite field

Authors: Antonio Cafure and Guillermo Matera
Journal: Math. Comp. 75 (2006), 2049-2085
MSC (2000): Primary 11G25, 14G05, 68W30; Secondary 11G20, 13P05, 68Q10, 68Q25
Published electronically: July 20, 2006
MathSciNet review: 2240649
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11G25, 14G05, 68W30, 11G20, 13P05, 68Q10, 68Q25

Retrieve articles in all journals with MSC (2000): 11G25, 14G05, 68W30, 11G20, 13P05, 68Q10, 68Q25

Additional Information

Antonio Cafure
Affiliation: Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Ciudad Universitaria, Pabellón I (1428) Buenos Aires, Argentina

Guillermo Matera
Affiliation: Instituto del Desarrollo Humano, Universidad Nacional de General Sarmiento, J.M. Gutiérrez 1150 (1613) Los Polvorines, Buenos Aires, Argentina; and National Council of Science and Technology (CONICET), Argentina

Keywords: Varieties over finite fields, rational points, geometric solutions, straight-line programs, probabilistic algorithms, first Bertini theorem.
Received by editor(s): December 10, 2003
Received by editor(s) in revised form: October 10, 2005
Published electronically: July 20, 2006
Additional Notes: This research was partially supported by the following grants: UBACyT X112, PIP CONICET 2461, and UNGS 30/3005
Dedicated: Dedicated to Joos Heintz on the occasion of his 60th birthday
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.