# Testing compositeness of the order of an elliptic curve over a prime field

Assume an elliptic curve equation in short Weierstrass form $$y^2=x^3+a\,x+b$$ in a prime field $$\mathbb F_p$$ for small given $$a,b$$ (e.g. $$a=3$$, $$b=2$$) and given large primes $$p$$ (e.g. 256-bit). We want to determine if the order $$n$$ of the curve is composite for a given $$p$$. And we'd like that test to be quick on average in the affirmative, for we are actually searching for the rare $$p$$ making $$n$$ prime [update: and the twist order $$p+2-n$$ prime, which makes suitable $$p$$ quite rare, much like safe primes. The overall goal is curves suitable for Burt Kaliski's One-way permutations on elliptic curves].

There must be methods faster than firing the full Schoof–Elkies–Atkin to find $$n$$, followed by a primality test of $$n$$: at least, SEA determines $$n$$ modulo small primes, and if one of these moduli is $$0$$, then $$n$$ is composite. Unfortunately the implementation of SEA built in Sage reportedly has no provision for such early abort and it's hard to add one.

Is there some pseudoprime tests for the (unknown) $$n$$?

Is there there any hope with the following blueprint: we test if the order is divisible by small primes $$q$$, by writing some polynomial (system of?) equation(s) that the coordinates of a point $$R$$ of the curve must match if $$q\,R=\infty$$, and check if it has a solution in $$\mathbb F_p$$, in which case we proved that $$n$$ is composite?

I include code so this doesn't fit well as a comment, but it's not actually a complete answer.

I was curious how long doing this relatively naively in Sage would be. So I took $$E: y^2 = x^3 + 3x + 2$$ and computed the order over the finite field with the smallest prime above $$2^{256}$$. This returns pretty quickly for me.

# Sage code - version 10.0.rc1 2023-04-28, python 3.11.1
E = EllipticCurve([3, 2])

E
# Elliptic Curve defined by y^2 = x^3 + 3*x + 2 over Rational Field

E.Np(next_prime(2^256))
# 115792089237316195423570985008687907853629405411711892692210002027599850173968

%time E.Np(next_prime(10^78))  # some larger prime
# Wall time: 1.62 s


What sage is actually doing here is calling PariGP, and I have no idea what PariGP is doing. But I think a couple of seconds for such a computation seems pretty reasonable.

Actually, it probably would take longer to show such an order is prime than to compute it. It would typically be very fast to use a probable prime test to verify that composite orders are composite though (using, for example, is_pseudoprime -- which uses PariGP's Baillie-PSW probabilistic primality test; no known pseudoprimes exist, but infinitely many are conjectured to exist. If you find one, share it with the world!).

• I have added why I want speed: I'm looking for $n$ and $2p+2-n$ (the twist's order) both prime. The overall goal is curves suitable for Burt Kaliski's One-way permutations on elliptic curves. Commented Feb 6 at 21:36