Ask Your Question
0

Quick check that an elliptic curve has composite order

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

fgrieu gravatar image

updated 2024-02-06 14:23:24 +0100

FrédéricC gravatar image

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 flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted
1

answered 2024-02-06 13:02:15 +0100

Luca gravatar image

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.

edit flag offensive delete link 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.

fgrieu gravatar imagefgrieu ( 2024-02-06 19:02:57 +0100 )edit
0

answered 2024-02-09 03:54:27 +0100

Max Alekseyev gravatar image

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

edit flag offensive delete link more

Comments

1

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

fgrieu gravatar imagefgrieu ( 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

Question Tools

1 follower

Stats

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

Seen: 158 times

Last updated: Feb 09