Séminaire des équipes-projets

On the Distribution of Atkin and Elkies Primes

  • Date : 26/01/2012
  • Lieu : École Normale Supérieure, Amphi Évariste Galois - NIR
  • Intervenants : Igor Shparlinski (Macquarie Univ., Australia)
  • Organisateurs : 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

Mots-clés : Cryptographie Séminaire Équipe-projet CASCADE

Haut de page

Siège et centres de recherche Inria

Accès direct

Social