2
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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!).

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Feb 6 at 21:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .