On the Product of Small Elkies Primes

2013/01/01 by Igor Shparlinski, Shparlinski, Igor
Computer Science · Mathematics · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #cs.CR #math.NT

paper · pdf · doi:10.48550/arxiv.1301.0035

arxiv created 2013/01/01 · arxiv updated 2013/01/03

Abstract

Given an elliptic curve E over a finite field \F_q of q elements, we say that an odd prime ℓ \nmid q is an Elkies prime for E if t_E² - 4q is a quadratic residue modulo ℓ, where t_E = q+1 - #E(\F_q) and #E(\F_q) is the number of \F_q-rational points on E. These primes are used in the presently most efficient algorithm to compute #E(\F_q). In particular, the bound L_q(E) such that the product of all Elkies primes for E up to L_q(E) exceeds 4q^1/2 is a crucial parameter of this algorithm. We show that there are infinitely many pairs (p, E) of primes p and curves E over \F_p with L_p(E) ≥ c log p log log log p for some absolute constant c>0, while a naive heuristic estimate suggests that L_p(E) ∼ log p. This complements recent results of Galbraith and Satoh (2002), conditional under the Generalised Riemann Hypothesis, and of Shparlinski and Sutherland (2012), unconditional for almost all pairs (p,E).

Related

• The Counting function for Elkies primes
• The asymptotic distribution of Elkies primes for reductions of abelian varieties is Gaussian
• Factoring integer using elliptic curves over rational number field ℚ
• Non-CM elliptic curves with infinitely many almost prime Frobenius traces
• Almost prime values of the order of abelian varieties over finite fields