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...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Artículo publishedVersion |
| Lenguaje: | Inglés |
| Publicado: |
2006
|
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_00255718_v75_n256_p2049_Cafure |
| Aporte de: |
| id |
paperaa:paper_00255718_v75_n256_p2049_Cafure |
|---|---|
| record_format |
dspace |
| spelling |
paperaa:paper_00255718_v75_n256_p2049_Cafure2023-06-12T16:45:08Z Fast computation of a rational point of a variety over a finite field Math. Comput. 2006;75(256):2049-2085 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. 2006 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng 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) |
| language |
Inglés |
| orig_language_str_mv |
eng |
| 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 |
Artículo Artículo publishedVersion |
| 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 |
| publishDate |
2006 |
| 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_ |
1769810097400184832 |