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 |
| Summary: | 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. |
|---|