Enumerating hyperelliptic curves over finite fields in quasilinear time
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929392777691136 |
|---|---|
| author | Howe, Everett W. |
| author_facet | Howe, Everett W. |
| contents | We present an algorithm that, for every fixed genus $g$, will enumerate all hyperelliptic curves of genus $g$ over a finite field $k$ of odd characteristic in quasilinear time; that is, the time required for the algorithm is $\widetilde{O}(q^{2g-1})$, where $q=\#k$. Such an algorithm already exists in the case $g=2$, thanks to work of Mestre and Cardona and Quer, and in the case $g=3$, thanks to work of Lercier and Ritzenthaler. Experimentally, it appears that our new algorithm is about two orders of magnitude faster in practice than ones based on their work. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_15255 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Enumerating hyperelliptic curves over finite fields in quasilinear time Howe, Everett W. Number Theory 11G20 (Primary) 11Y16, 14G15, 14H10, 14H25 (Secondary) We present an algorithm that, for every fixed genus $g$, will enumerate all hyperelliptic curves of genus $g$ over a finite field $k$ of odd characteristic in quasilinear time; that is, the time required for the algorithm is $\widetilde{O}(q^{2g-1})$, where $q=\#k$. Such an algorithm already exists in the case $g=2$, thanks to work of Mestre and Cardona and Quer, and in the case $g=3$, thanks to work of Lercier and Ritzenthaler. Experimentally, it appears that our new algorithm is about two orders of magnitude faster in practice than ones based on their work. |
| title | Enumerating hyperelliptic curves over finite fields in quasilinear time |
| topic | Number Theory 11G20 (Primary) 11Y16, 14G15, 14H10, 14H25 (Secondary) |
| url | https://arxiv.org/abs/2401.15255 |