Counting points on hyperelliptic curves in average polynomial time
Counting points on hyperelliptic curves in average polynomial time
复制标题
在平均多项式时间内计算超椭圆曲线上的点
DOI：
10.4007/annals.2014.179.2.7
复制
发表时间：
2012
影响因子：
4.9
通讯作者：
David Harvey
中科院分区：
文献类型：
--
作者：
David Harvey
设g 1，Q2 Z[x]是一个单调的，无平方因子的2g + 1次多项式.对于不整除Q的判别式的奇素数p，设Zp（T）表示有限域Fp上亏格g的超椭圆曲线的zeta函数，通过约化方程y2 = Q（x）模p的系数得到.给出了一个以Q和正整数N为输入的显式确定性算法，对所有p < N的素数同时计算Zp（T），其每个素数的平均复杂度是g的多项式，logN，以及表示Q所需的位数。
Let g 1, and let Q2 Z[x] be a monic, squarefree polynomial of degree 2g + 1. For an odd prime p not dividing the discriminant of Q, let Zp(T ) denote the zeta function of the hyperelliptic curve of genus g over the nite eld Fp obtained by reducing the coecients of the equation y 2 = Q(x) modulo p. We present an explicit deterministic algorithm that given as input Q and a positive integer N, computes Zp(T ) simultaneously for all such primes p < N, whose average complexity per prime is polynomial in g, logN, and the number of bits required to represent Q.