摘要翻译:
本文给出了定义在基数为$q$的有限域上的一般普通超椭圆曲线的Jacobian变体上有理点数的计算算法,其时间复杂度为$O(n^{2+O(1)})$,空间复杂度为$O(n^2)$,其中$n=\log(q)$。在后一种复杂度估计中,假定属和特征是固定的。我们的算法形成了两者的推广,即J.-F.的AGM算法。Mestre和T.satoh的正则提升法。我们用θ常数正则地提升了超椭圆曲线雅可比的一个算术不变量。theta空值是根据级别为$2^\nu p$的半规范theta结构计算的,其中$\nu>0$是整数,$p=\mathrm{char}(\f_q)>2$。本文的结果对有限域上定义的泛型普通阿贝尔变式有理点数是否存在拟二次时间算法的问题给出了全局肯定的回答。
---
英文标题:
《A p-adic quasi-quadratic point counting algorithm》
---
作者:
Robert Carls, David Lubicz
---
最新提交年份:
2008
---
分类信息:
一级分类:Mathematics 数学
二级分类:Number Theory 数论
分类描述:Prime numbers, diophantine equations, analytic number theory, algebraic number theory, arithmetic geometry, Galois theory
素数,丢番图方程,解析数论,代数数论,算术几何,伽罗瓦理论
--
一级分类:Mathematics 数学
二级分类:Algebraic Geometry 代数几何
分类描述:Algebraic varieties, stacks, sheaves, schemes, moduli spaces, complex geometry, quantum cohomology
代数簇,叠,束,格式,模空间,复几何,量子上同调
--
---
英文摘要:
In this article we give an algorithm for the computation of the number of rational points on the Jacobian variety of a generic ordinary hyperelliptic curve defined over a finite field of cardinality $q$ with time complexity $O(n^{2+o(1)})$ and space complexity $O(n^2)$, where $n=\log(q)$. In the latter complexity estimate the genus and the characteristic are assumed as fixed. Our algorithm forms a generalization of both, the AGM algorithm of J.-F. Mestre and the canonical lifting method of T. Satoh. We canonically lift a certain arithmetic invariant of the Jacobian of the hyperelliptic curve in terms of theta constants. The theta null values are computed with respect to a semi-canonical theta structure of level $2^\nu p$ where $\nu >0$ is an integer and $p=\mathrm{char}(\F_q)>2$. The results of this paper suggest a global positive answer to the question whether there exists a quasi-quadratic time algorithm for the computation of the number of rational points on a generic ordinary abelian variety defined over a finite field.
---
PDF链接:
https://arxiv.org/pdf/0706.0234