Counting points on abelian surfaces over finite fields with Elkies's method

2022/03/03 by Jean Kieffer, Kieffer, Jean
Computer Science · Mathematics · #11-04 #11T71 #11Y16 #14K02 #Coding theory and cryptography #Cryptography and Residue Arithmetic #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #cs.CR #math.NT #msc:11-04 #msc:11T71 #msc:11Y16 #msc:14K02

paper · pdf · doi:10.48550/arxiv.2203.02009

Results improve on the author's PhD thesis

arxiv created 2022/03/03 · openalex publication_date 2022/03/03 · arxiv updated 2022/03/07 · openalex created_date 2022/04/03 · openalex updated_date 2026/07/28

Abstract

We generalize Elkies's method, an essential ingredient in the SEA algorithm to count points on elliptic curves over finite fields of large characteristic, to the setting of p.p. abelian surfaces. Under reasonable assumptions related to the distribution of Elkies primes, we obtain improvements over Schoof's method in two cases. If the abelian surface A over Fq has RM by a fixed quadratic field F, we reach the same asymptotic complexity Otilde(log4 q) as the SEA algorithm up to constant factors depending on F. If A is defined over a number field, we count points on A modulo sufficiently many primes in Otilde(log6 q) binary operations on average. Numerical experiments demonstrate the practical usability of our methods.

Cited by

• Evaluating modular equations for abelian surfaces

Related

• The Counting function for Elkies primes
• The asymptotic distribution of Elkies primes for reductions of abelian varieties is Gaussian
• On Elkies subgroups of l-torsion points in elliptic curves defined over a finite field
• Counting points on curves over families in polynomial time
• Number of points on abelian and Jacobian varieties over finite fields