## Abstract

Given an elliptic curve E over a finite field F_{q} of q elements, we say that an odd prime ℓ {does not divide} q is an Elkies prime for E if t_{E}^{2} - 4q is a square modulo ℓ, where (Formula presented.) is the number of F_{q}-rational points on E; otherwise, ℓ is called an Atkin prime. We show that there are asymptotically the same number of Atkin and Elkies primes ℓ < L on average over all curves E over F_{q}, provided that L ≥ (log q)^{ε} for any fixed ε > 0 and a sufficiently large q. We use this result to design and analyze a fast algorithm to generate random elliptic curves with #E(F_{p}) prime, where p varies uniformly over primes in a given interval [x, 2x].

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

Pages (from-to) | 285-297 |

Number of pages | 13 |

Journal | Foundations of Computational Mathematics |

Volume | 14 |

Issue number | 2 |

DOIs | |

Publication status | Published - Apr 2014 |

Externally published | Yes |

## Keywords

- Character sum
- Elkies prime
- Elliptic curve