4
$\begingroup$

Suppose we have some elliptic curve defined over $\mathbb F_p$, with $p$ a large prime. Let $n$ be the number of points on the curve. I am interested in what is currently known about the probability* that $n$ is prime (i.e. some reasonable lower bound on this probability).

$n$ is well-known to be within the "Hasse-Weil interval": $$t := \left| n - (p + 1) \right| \le 2 \sqrt p$$

By PNT there are something like $\frac {4 \sqrt p} {\log p}$ primes in this interval, but obviously the probability distribution of $t$ in this interval is non-uniform, so this does not directly give us a good bound. Is there perhaps some known constant multiple of this that is a correct bound?

*Note: To clarify the meaning of "probability": Suppose that the curve was chosen at random (uniformly) from all the nonsingular elliptic curves of form $y^2 = x^3 + ax + b$ over $\mathbb F_p$.

$\endgroup$
  • 1
    $\begingroup$ "but obviously the probability distribution of $t$ in this interval is non-uniform". I am not saying you are wrong, but I don't see why it is obvious. $\endgroup$ – corpsfini Feb 12 at 11:38
  • $\begingroup$ Ok, maybe the word obvious is a bit too much here, but from what I've read on the subject I understood that it's known and basic. $\endgroup$ – Yoni Rozenshein Feb 12 at 16:58
5
$\begingroup$

It is known, that as in your setting, when $p$ is prime every possible integer in the Hasse-interval $\mathcal{H}_p$ arises as group order of an elliptic curve $E/\mathbb{F}_p$. For arbitrary prime powers $q = p^f$ this is not generally true: there are often not enough supersingular curves to cover the cases $N \equiv 1 \mod p$.

Galbraith and McKee gives a formula for the probability that a randomly chosen elliptic curve over a finite field has a prime number of points. The conjecture is the following: Let $P_1$ be the probability that a number within $\mathcal{H}_p$ is prime. Let $C_2\approx0.6601$ be the Hardy-Littlewood twin primes constant. Then the probability that an elliptic curve over $\mathbb{F}_p$ has a prime number of points is asymptotic to $c_pP_1$ as $p\to \infty$, where

$$c_p=\frac{3}{2}C_2\prod_{l\vert p-1,l>2}\Big(1+\frac{1}{(l+1)(l-2)}\Big) .$$

One might say that $P_1\approx\frac{1}{\log p}$, however this estiamte might not be precise in short intervals.

If all numbers of points in $\mathcal{H}_p$ were equally likely, then we would have $c_p = 1$. The expression given for $c_p$ lies between about $0.44$ and $0.62$, indicating the phenomenon that prime numbers of points are disfavoured.

Even though prime numbers of points are seem to be disfavoured by nature, you can efficiently generate such curves in poly-time, ie. in $\mathcal{O}(\log^{3} p)$.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.