## Abstract

Given an elliptic curve E over a finite field F_{q} of q elements, we say that an odd prime ℓ + q is an Elkies prime for E if t^{2} _{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. The Elkies primes are used in the presently most efficient algorithm to compute #E(F_{q}). In particular, the quantity L_{q}(E) defined as the smallest L such that the product of all Elkies primes for E up to L 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 upper bounds on L_{q}(E) proposed by Galbraith and Satoh in 2002, conditional under the Generalised Riemann Hypothesis, and by Shparlinski and Sutherland in 2011, unconditional for almost all pairs (p,E).

Original language | English |
---|---|

Pages (from-to) | 1441-1448 |

Number of pages | 8 |

Journal | Proceedings of the American Mathematical Society |

Volume | 143 |

Issue number | 4 |

DOIs | |

Publication status | Published - 2015 |

## Keywords

- Character sums
- Elkies primes
- Elliptic curves