Counting points on smooth plane quartics
Abstract We present efficient algorithms for counting points on a smooth plane quartic curve X modulo a prime p. We address both the case where X is defined over $${\mathbb {F}}_p$$...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer International Publishing
2022
|
| Online Access: | https://hdl.handle.net/1721.1/146631 |
| _version_ | 1826216552529133568 |
|---|---|
| author | Costa, Edgar Harvey, David Sutherland, Andrew V. |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Costa, Edgar Harvey, David Sutherland, Andrew V. |
| author_sort | Costa, Edgar |
| collection | MIT |
| description | Abstract
We present efficient algorithms for counting points on a smooth plane quartic curve X modulo a prime p. We address both the case where X is defined over
$${\mathbb {F}}_p$$
F
p
and the case where X is defined over
$${\mathbb {Q}}$$
Q
and p is a prime of good reduction. We consider two approaches for computing
$$\#X({\mathbb {F}}_p)$$
#
X
(
F
p
)
, one which runs in
$$O(p\log p\log \log p)$$
O
(
p
log
p
log
log
p
)
time using
$$O(\log p)$$
O
(
log
p
)
space and one which runs in
$$O(p^{1/2}\log ^2p)$$
O
(
p
1
/
2
log
2
p
)
time using
$$O(p^{1/2}\log p)$$
O
(
p
1
/
2
log
p
)
space. Both approaches yield algorithms that are faster in practice than existing methods. We also present average polynomial-time algorithms for
$$X/{\mathbb {Q}}$$
X
/
Q
that compute
$$\#X({\mathbb {F}}_p)$$
#
X
(
F
p
)
for good primes
$$p\leqslant N$$
p
⩽
N
in
$$O(N\log ^3 N)$$
O
(
N
log
3
N
)
time using O(N) space. These are the first practical implementations of average polynomial-time algorithms for curves that are not cyclic covers of
$${\mathbb {P}}^1$$
P
1
, which in combination with previous results addresses all curves of genus
$$g\leqslant 3$$
g
⩽
3
. Our algorithms also compute Cartier–Manin/Hasse–Witt matrices that may be of independent interest. |
| first_indexed | 2024-09-23T16:49:28Z |
| format | Article |
| id | mit-1721.1/146631 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:49:28Z |
| publishDate | 2022 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1466312023-08-31T20:22:03Z Counting points on smooth plane quartics Costa, Edgar Harvey, David Sutherland, Andrew V. Massachusetts Institute of Technology. Department of Mathematics Abstract We present efficient algorithms for counting points on a smooth plane quartic curve X modulo a prime p. We address both the case where X is defined over $${\mathbb {F}}_p$$ F p and the case where X is defined over $${\mathbb {Q}}$$ Q and p is a prime of good reduction. We consider two approaches for computing $$\#X({\mathbb {F}}_p)$$ # X ( F p ) , one which runs in $$O(p\log p\log \log p)$$ O ( p log p log log p ) time using $$O(\log p)$$ O ( log p ) space and one which runs in $$O(p^{1/2}\log ^2p)$$ O ( p 1 / 2 log 2 p ) time using $$O(p^{1/2}\log p)$$ O ( p 1 / 2 log p ) space. Both approaches yield algorithms that are faster in practice than existing methods. We also present average polynomial-time algorithms for $$X/{\mathbb {Q}}$$ X / Q that compute $$\#X({\mathbb {F}}_p)$$ # X ( F p ) for good primes $$p\leqslant N$$ p ⩽ N in $$O(N\log ^3 N)$$ O ( N log 3 N ) time using O(N) space. These are the first practical implementations of average polynomial-time algorithms for curves that are not cyclic covers of $${\mathbb {P}}^1$$ P 1 , which in combination with previous results addresses all curves of genus $$g\leqslant 3$$ g ⩽ 3 . Our algorithms also compute Cartier–Manin/Hasse–Witt matrices that may be of independent interest. 2022-11-28T15:34:32Z 2022-11-28T15:34:32Z 2022-11-21 2022-11-27T04:12:35Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/146631 Research in Number Theory. 2022 Nov 21;9(1):1 PUBLISHER_CC en https://doi.org/10.1007/s40993-022-00397-8 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer International Publishing Springer International Publishing |
| spellingShingle | Costa, Edgar Harvey, David Sutherland, Andrew V. Counting points on smooth plane quartics |
| title | Counting points on smooth plane quartics |
| title_full | Counting points on smooth plane quartics |
| title_fullStr | Counting points on smooth plane quartics |
| title_full_unstemmed | Counting points on smooth plane quartics |
| title_short | Counting points on smooth plane quartics |
| title_sort | counting points on smooth plane quartics |
| url | https://hdl.handle.net/1721.1/146631 |
| work_keys_str_mv | AT costaedgar countingpointsonsmoothplanequartics AT harveydavid countingpointsonsmoothplanequartics AT sutherlandandrewv countingpointsonsmoothplanequartics |