论文标题
平滑平面四分之一的计数点
Counting points on smooth plane quartics
论文作者
论文摘要
我们提出有效的算法，用于平滑平面四分之一曲线上的计数点$ x $ modulo a Prime $ p $。我们解决了$ x $在$ \ Mathbb f_p $上定义的情况，以及$ x $在$ \ Mathbb Q $和$ p $上定义的情况是很好的减少。我们考虑了两种用于计算$ \＃x（\ mathbb f_p）$的方法，一种在$ o（p \ log p \ log p \ log \ log \ log p）$ time使用$ o（\ log p）$ space和一种以$ o（p^{1/2}} \ log^2 \！p）$ o（p^2 \！p）$ o（p^p）$ o（p^p）$ o（p^p^p^p^p^p^p^1/2}}中。两种方法都产生的算法在实践中比现有方法更快。我们还提出了$ x/\ mathbb Q $的平均多项式时间算法，该算法计算$ \＃x（\ m马理bb f_p）$ for primes $ p \ le n $ in $ o（n \ log^3 \！n）$ o（n \ log^3 \！n）$ time使用$ o（n）$ space。这些是曲线的平均多项式时间算法的第一个实际实现，这些算法不是$ \ Mathbb p^1 $的循环覆盖物，与先前的结果相结合，它解决了$ g \ le 3 $的所有曲线。我们的算法还计算了可能具有独立关注的卡地亚甘油/hasse-witt矩阵。
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$ and the case where $X$ is defined over $\mathbb Q$ and $p$ is a prime of good reduction. We consider two approaches for computing $\#X(\mathbb F_p)$, one which runs in $O(p\log p\log\log p)$ time using $O(\log p)$ space and one which runs in $O(p^{1/2}\log^2\!p)$ time using $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$ that compute $\#X(\mathbb F_p)$ for good primes $p\le N$ in $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$, which in combination with previous results addresses all curves of genus $g\le 3$. Our algorithms also compute Cartier-Manin/Hasse-Witt matrices that may be of independent interest.
