SUBTLETIES IN THE DISTRIBUTION OF THE NUMBERS OF POINTS ON ELLIPTIC CURVES OVER A FINITE PRIME FIELD

Abstract

Three questions concerning the distribution of the numbers of points on elliptic curves over a finite prime field are considered. First, the previously published bounds for the distribution are tightened slightly. Within these bounds, there are wild fluctuations in the distribution, and some heuristics are discussed (supported by numerical evidence) which suggest that numbers of points with no large prime divisors are unusually prevalent. Finally, allowing the prime field to vary while fixing the field of fractions of the endomorphism ring of the curve, the order of magnitude of the average order of the number of divisors of the number of points is determined, subject to assumptions about primes in quadratic progressions.

There are implications for factoring integers by Lenstra's elliptic curve method. The heuristics suggest that (i) the subtleties in the distribution actually favour the elliptic curve method, and (ii) this gain is transient, dying away as the factors to be found tend to infinity.