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 |
| Publicado: |
2006
|
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_00255718_v75_n256_p2049_Cafure https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_00255718_v75_n256_p2049_Cafure_oai |
| Aporte de: |
| id |
I28-R145-paper_00255718_v75_n256_p2049_Cafure_oai |
|---|---|
| record_format |
dspace |
| spelling |
I28-R145-paper_00255718_v75_n256_p2049_Cafure_oai2024-08-16 Cafure, A. Matera, G. 2006 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. application/pdf http://hdl.handle.net/20.500.12110/paper_00255718_v75_n256_p2049_Cafure info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Math. Comput. 2006;75(256):2049-2085 First Bertini theorem Geometric solutions Probabilistic algorithms Rational points Straight-line programs Varieties over finite fields Fast computation of a rational point of a variety over a finite field info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_00255718_v75_n256_p2049_Cafure_oai |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-145 |
| collection |
Repositorio Digital de la Universidad de Buenos Aires (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 |
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 https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_00255718_v75_n256_p2049_Cafure_oai |
| work_keys_str_mv |
AT cafurea fastcomputationofarationalpointofavarietyoverafinitefield AT materag fastcomputationofarationalpointofavarietyoverafinitefield |
| _version_ |
1809357078477668352 |