The Counting function for Elkies primes

2023/11/28 by Meher Elijah Lippmann, Lippmann, Meher Elijah, Kevin J. McGown +1
Computer Science · Mathematics · #11L40 #11N05 (Primary) 11L20 #11T71 #11Y16 #14H52 (Secondary) #Analytic Number Theory Research #Bounded function #Coding theory and cryptography #Combinatorics #Cryptography and Residue Arithmetic #Discrete mathematics #Distribution (mathematics) #FOS: Mathematics #Function (biology) #Mathematical analysis #Mathematics #Number Theory (math.NT) #Prime (order theory) #Prime number #Prime number theorem #Upper and lower bounds

paper · pdf · doi:10.48550/arxiv.2311.17231

openalex publication_date 2023/11/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let E be an elliptic curve over a finite field \mathbbF_q where q is a prime power. The Schoof--Elkies--Atkin (SEA) algorithm is a standard method for counting the number of \mathbbF_q-points on E. The asymptotic complexity of the SEA algorithm depends on the distribution of the so-called Elkies primes. Assuming GRH, we prove that the least Elkies prime is bounded by (2log 4q+4)² when q≥ 10⁹. This is the first such explicit bound in the literature. Previously, Satoh and Galbraith established an upper bound of O((log q)^2+ε). Let N_E(X) denote the number of Elkies primes less than X. Assuming GRH, we also show N_E(X)=(π(X))/(2)+O((√(X)(log qX)²)/(log X)) .

Related

• On the Product of Small Elkies Primes
• Counting points on abelian surfaces over finite fields with Elkies's method
• 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
• Elliptic Gauß sums and Schoof's algorithm