First time here? Check out the FAQ!

Ask Your Question
0

Quick check that an elliptic curve has composite order

asked 1 year ago

fgrieu gravatar image

updated 1 year ago

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.

Preview: (hide)

2 Answers

Sort by » oldest newest most voted
1

answered 1 year ago

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.

Preview: (hide)
link

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 ( 1 year ago )
0

answered 1 year ago

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

Preview: (hide)
link

Comments

1

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

fgrieu gravatar imagefgrieu ( 0 years ago )

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: 1 year ago

Seen: 193 times

Last updated: Feb 09 '24