Counting points on hyperelliptic curves in average polynomial time

• 成果类型: Article
• 署名作者: Harvey, David
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2014.179.2.7
• 发表日期: 2014
• 页码: 783-803
• 关键词: abelian-varieties; elliptic-curves; finite-fields; roots

摘要

Let g >= 1, and let Q is an element of Z[x] be a monic, squarefree polynomial of degree 2g + 1. For an odd prime p not dividing the discriminant of Q, let Z(p)(T) denote the zeta function of the hyperelliptic curve of genus g over the finite field F-p obtained by reducing the coefficients 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 Z(p)(T) simultaneously for all such primes p < N, whose average complexity per prime is polynomial in g, log N, and the number of bits required to represent Q.