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.
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.
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").
Asked: 2024-02-06 11:03:25 +0100
Seen: 186 times
Last updated: Feb 09
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
