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

Mostrar todas las versiones(3)

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, A., Matera, G.
Formato: JOUR
Materias:
First Bertini theorem
Geometric solutions
Probabilistic algorithms
Rational points
Straight-line programs
Varieties over finite fields
Acceso en línea: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 todo:paper_00255718_v75_n256_p2049_Cafure
record_format dspace
spelling todo:paper_00255718_v75_n256_p2049_Cafure2023-10-03T14:36:12Z Fast computation of a rational point of a variety over a finite field Cafure, A. Matera, G. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, A.
Matera, G.
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.
format JOUR
author Cafure, A.
Matera, G.
author_facet Cafure, A.
Matera, G.
author_sort Cafure, A.
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
url http://hdl.handle.net/20.500.12110/paper_00255718_v75_n256_p2049_Cafure
work_keys_str_mv AT cafurea fastcomputationofarationalpointofavarietyoverafinitefield
AT materag fastcomputationofarationalpointofavarietyoverafinitefield
_version_ 1807318668729647104

Ejemplares similares