Ask Your Question

# Quick check that an elliptic curve has composite order

Assume E is an Elliptic Curve over the field Fp, with p a known prime, for example as obtained by

p = next_prime(p)
F = GF(p)
E = EllipticCurve([F(3),F(2)])


Is there a much faster way to check that E is of composite order (the most common case) than using the obvious

not E.cardinality().is_prime()


That could speed up the search of prime-order curves.

edit retag close merge delete

## 2 Answers

Sort by » oldest newest most voted

No, there is not.

The Schoof-Elkies-Atkin algorithm actually computes the order of the curve modulo small primes, and then puts the final result together via CRT, so in principle you could modify it to early-abort if it is found that the order is 0 modulo one of the small primes, but to get the final answer you still need to compute the whole order and check whether it is prime. Sage calls the Schoof-Elkies-Atkin implementation in Pari/GP for point counting, so this modification wouldn't be easy to do.

more

## Comments

Thanks. The built-in partial SEA with early abort is one thing I was hopping for, and this shows it's not available. I wonder is there is hope otherwise, like checking if the order has a small divisor by some method.

( 2024-02-06 19:02:57 +0100 )edit

Use .is_pseudoprime() instead of .is_prime(). It can be much faster for large numbers, and there are no known cases of an error (when a composite number called "prime").

more

## Comments

True, but in practice for sizable p, most of the time is spent in cardinality, not is_prime.

( 2024-02-20 15:06:12 +0100 )edit

## Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

## Stats

Asked: 2024-02-06 11:03:25 +0100

Seen: 64 times

Last updated: Feb 09