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

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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Cafure, Antonio Artemio, Matera, Guillermo
Publicado:	2006
Materias:	First Bertini theorem Geometric solutions Probabilistic algorithms Rational points Straight-line programs Varieties over finite fields
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00255718_v75_n256_p2049_Cafure http://hdl.handle.net/20.500.12110/paper_00255718_v75_n256_p2049_Cafure
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_00255718_v75_n256_p2049_Cafure
record_format	dspace
spelling	paper:paper_00255718_v75_n256_p2049_Cafure2023-06-08T14:53:14Z Fast computation of a rational point of a variety over a finite field Cafure, Antonio Artemio Matera, Guillermo First Bertini theorem Geometric solutions Probabilistic algorithms Rational points Straight-line programs Varieties over finite fields 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. © 2006 American Mathematical Society. Fil:Cafure, A. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Matera, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2006 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00255718_v75_n256_p2049_Cafure http://hdl.handle.net/20.500.12110/paper_00255718_v75_n256_p2049_Cafure
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	First Bertini theorem Geometric solutions Probabilistic algorithms Rational points Straight-line programs Varieties over finite fields
spellingShingle	First Bertini theorem Geometric solutions Probabilistic algorithms Rational points Straight-line programs Varieties over finite fields Cafure, Antonio Artemio Matera, Guillermo Fast computation of a rational point of a variety over a finite field
topic_facet	First Bertini theorem Geometric solutions Probabilistic algorithms Rational points Straight-line programs Varieties over finite fields
description	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. © 2006 American Mathematical Society.
author	Cafure, Antonio Artemio Matera, Guillermo
author_facet	Cafure, Antonio Artemio Matera, Guillermo
author_sort	Cafure, Antonio Artemio
title	Fast computation of a rational point of a variety over a finite field
title_short	Fast computation of a rational point of a variety over a finite field
title_full	Fast computation of a rational point of a variety over a finite field
title_fullStr	Fast computation of a rational point of a variety over a finite field
title_full_unstemmed	Fast computation of a rational point of a variety over a finite field
title_sort	fast computation of a rational point of a variety over a finite field
publishDate	2006
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00255718_v75_n256_p2049_Cafure http://hdl.handle.net/20.500.12110/paper_00255718_v75_n256_p2049_Cafure
work_keys_str_mv	AT cafureantonioartemio fastcomputationofarationalpointofavarietyoverafinitefield AT materaguillermo fastcomputationofarationalpointofavarietyoverafinitefield
_version_	1768543169927970816

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

Ejemplares similares