Inria
Inria.fr
Inria Channel
Séminaire des équipes-projets
On the Distribution of Atkin and Elkies Primes
- Date : 26/01/2012
- Place : École Normale Supérieure, Amphi Évariste Galois - NIR
- Guests : Igor Shparlinski (Macquarie Univ., Australia)
- Organisers : Cascade
Given an elliptic curve E over a finite field F$_q$ of q elements, we say that an odd prime l not dividing q is an Elkies prime for E if t$_E^2$ - 4q is a square modulo l, where t$_E$ = q+1 - #E(F$_q$) and #E(F$_q$) is the number of F$_q$-rational points on E; otherwise l is called an Atkin prime.
We show that there are asymptotically the same number of Atkin and Elkies primes l < L on average over all curves E over F$_q$, provided that L >= (log q)$^\varepsilon$ for any fixed $\varepsilon$>0 and a sufficiently large q. We use this result to design and analyse 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].
Joint work with Andrew Sutherland
Keywords: Cryptographie Séminaire Équipe-projet CASCADE
