1
$\begingroup$

An elliptic curve defined over a finite field is either cyclic, or a direct sum of two cyclic groups. In cryptography, we use exclusively the former. I was wondering if there is any result on how common (or rare) are rank-2 elliptic curves defined over $\mathbb{F}_{q}$ for a prime power $q$.

(They don't seem rare. For a fixed prime $p$ of 64 bits, I sampled 1000 random curves defined over $\mathbb{F}_p$ and got 170 curves of rank 2. Same experiment with a 128-bit $p$ yields 208 such curves. )

$\endgroup$
1
  • $\begingroup$ It's not true that we only use curves with cyclic group structure: Pairing-friendly curves have full $\ell$‑torsion defined over a small extension! It might not always be obvious with the way things are written down, but there's always an $E[\ell]=\mathbb Z/\ell\times\mathbb Z/\ell$ somewhere under the hood. $\endgroup$
    – yyyyyyy
    Jun 14, 2022 at 6:53

1 Answer 1

3
$\begingroup$

For prime $p$, let us denote by $C(p)$ the probability that a random elliptic curve $E/\mathbb{F}_p$ satisfies that $E(\mathbb{F}_p)$ is cyclic (this depends slightly on how one defines a “random” elliptic curve, but most reasonable ways—choosing the isomorphism class at random, choosing the $j$-invariant at random and then a random twist, choosing the short Weierstrass coefficients at random, etc.—should give basically the same result asymptotically). Then I claim that, for large $p$, we have: $$C(p) = \prod_{\ell |p-1} \Big(1-\frac{1}{\ell^3-\ell}\Big) + o(1), \tag{1}$$ where the product is over all the prime divisors of $p-1$ (and one could write a more precise bound for the error term if one wanted). This implies in particular that: $$\limsup_{p\to\infty} C(p) = 1-\frac{1}{2^3-2} = \frac{5}{6} \approx 0.833,$$ and: $$\liminf_{p\to\infty} C(p) = \prod_{\ell} \Big(1-\frac{1}{\ell^3-\ell}\Big) \approx 0.788.$$

This is because $E$ is non-cyclic (I don't think “rank 2” is a very good name for this) if and only if there exists a prime $\ell$ such that $E$ has full $\ell$-torsion over $\mathbb{F}_p$, or equivalently, such that the Frobenius endomorphism of $E$ acts as the identity on $E[\ell]$.

Now, standard equidistribution results (see e.g. Theorem 2 in this paper of Castryk and Hubrechts) say that, for fixed $\ell$ and large $p$, the Frobenius acting on $E[\ell]$ is essentially uniformly distributed among $2\times 2$ matrices of determinant $p$ over $\mathbb{F}_\ell$ as $E$ ranges over elliptic curves over $\mathbb{F}_p$. This means that the probability of getting the identity is $0$ if $p\not\equiv 1\pmod\ell$, and $1/\#\mathop{\textrm{SL}}_2(\mathbb{F}_\ell) = 1/(\ell^3-\ell)$ otherwise.

This gives formula $(1)$, and the lim inf and lim sup results are obtained by choosing large primes $p$ that are congruent to $1$ (resp., something else) modulo all the primes $\ell$ from $3$ to some arbitrarily large bound.

(And as you can see, the probability you get depends much more on what the factors of $p-1$ look like than on the size of $p$ per se).

$\endgroup$
2
  • $\begingroup$ Thanks Professor. Could you give a hint on why "rank 2" is not a good name for non-cyclic curves? $\endgroup$
    – zugzwang
    Jun 20, 2022 at 20:47
  • 1
    $\begingroup$ The rank of a $\mathbb{Z}$-module $M$ is usually defined as the dimension of the $\mathbb{Q}$-vector space $M\otimes_{\mathbb{Z}} \mathbb{Q}$,which for a torsion module is always zero. $\endgroup$ Jun 21, 2022 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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