On the Distribution of Atkin and Elkies Primes

Details On the Distribution of Atkin and Elkies Primes On the Distribution of Atkin and Elkies Primes

2011-12-14

arxiv.org/abs/1112.3390v2

Mathematics

Number Theory

17 pages, minor edits

Scientific paper

Given an elliptic curve E over a finite field F_q of q elements, we say that an odd prime ell not dividing q is an Elkies prime for E if t_E^2 - 4q is a square modulo ell, where t_E = q+1 - #E(F_q) and #E(F_q) is the number of F_q-rational points on E; otherwise ell is called an Atkin prime. We show that there are asymptotically the same number of Atkin and Elkies primes ell < L on average over all curves E over F_q, provided that L >= (log q)^e for any fixed e > 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].

Affiliated with

Also associated with

No associations

Rating

On the Distribution of Atkin and Elkies Primes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Distribution of Atkin and Elkies Primes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Distribution of Atkin and Elkies Primes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-561530