论文标题
平均多项式时间的超椭圆形曲线上的计数点
Counting points on superelliptic curves in average polynomial time
论文作者
论文摘要
我们描述了平均多项式时间算法的实际实现，用于在$ \ Mathbb Q $上定义的超椭圆形曲线上的计数点，其比以前的方法要快得多。我们的算法将输入作为超椭圆形曲线$ y^m = f（x）$，带有$ m \ ge 2 $和$ f \ in \ mathbb z [x] $ a $ d \ ge 3 $的任何SquareFree polyenorial ge 3 $，以及一个正整数$ n $。它可以计算所有$ p \ le n $ divinding $ m \ mathrm {lc}（f）（f）\ Mathrm {disc}（f）$ in time $ o（md^3 n \ log^3 n n \ log \ log \ log n）$。它通过计算Cartier-Manin矩阵的痕迹来实现这一目标。我们还可以计算Cartier-Manin矩阵本身，该矩阵本身决定了$ x $的jacobian的$ p $ - 列，并确定其Zeta函数模量〜$ p $的分子。
We describe the practical implementation of an average polynomial-time algorithm for counting points on superelliptic curves defined over $\mathbb Q$ that is substantially faster than previous approaches. Our algorithm takes as input a superelliptic curves $y^m=f(x)$ with $m\ge 2$ and $f\in \mathbb Z[x]$ any squarefree polynomial of degree $d\ge 3$, along with a positive integer $N$. It can compute $\#X(\mathbb F_p)$ for all $p\le N$ not dividing $m\mathrm{lc}(f)\mathrm{disc}(f)$ in time $O(md^3 N\log^3 N\log\log N)$. It achieves this by computing the trace of the Cartier--Manin matrix of reductions of $X$. We can also compute the Cartier--Manin matrix itself, which determines the $p$-rank of the Jacobian of $X$ and the numerator of its zeta function modulo~$p$.
