ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 20 Feb 2024 15:06:12 +0100Quick check that an elliptic curve has composite orderhttps://ask.sagemath.org/question/75838/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.Tue, 06 Feb 2024 11:03:25 +0100https://ask.sagemath.org/question/75838/quick-check-that-an-elliptic-curve-has-composite-order/Answer by Max Alekseyev for <p>Assume E is an Elliptic Curve over the field Fp, with p a known prime, for example as obtained by</p>
<pre><code>p = next_prime(p)
F = GF(p)
E = EllipticCurve([F(3),F(2)])
</code></pre>
<p>Is there a much faster way to check that E is of composite order (the most common case) than using the obvious</p>
<pre><code>not E.cardinality().is_prime()
</code></pre>
<p>That could speed up the search of prime-order curves.</p>
https://ask.sagemath.org/question/75838/quick-check-that-an-elliptic-curve-has-composite-order/?answer=75866#post-id-75866Use `.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").Fri, 09 Feb 2024 03:54:27 +0100https://ask.sagemath.org/question/75838/quick-check-that-an-elliptic-curve-has-composite-order/?answer=75866#post-id-75866Comment by fgrieu for <p>Use <code>.is_pseudoprime()</code> instead of <code>.is_prime()</code>. It can be much faster for large numbers, and there are no known cases of an error (when a composite number called "prime").</p>
https://ask.sagemath.org/question/75838/quick-check-that-an-elliptic-curve-has-composite-order/?comment=76115#post-id-76115True, but in practice for sizable `p`, most of the time is spent in `cardinality`, not `is_prime`.Tue, 20 Feb 2024 15:06:12 +0100https://ask.sagemath.org/question/75838/quick-check-that-an-elliptic-curve-has-composite-order/?comment=76115#post-id-76115Answer by Luca for <p>Assume E is an Elliptic Curve over the field Fp, with p a known prime, for example as obtained by</p>
<pre><code>p = next_prime(p)
F = GF(p)
E = EllipticCurve([F(3),F(2)])
</code></pre>
<p>Is there a much faster way to check that E is of composite order (the most common case) than using the obvious</p>
<pre><code>not E.cardinality().is_prime()
</code></pre>
<p>That could speed up the search of prime-order curves.</p>
https://ask.sagemath.org/question/75838/quick-check-that-an-elliptic-curve-has-composite-order/?answer=75840#post-id-75840No, 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.Tue, 06 Feb 2024 13:02:15 +0100https://ask.sagemath.org/question/75838/quick-check-that-an-elliptic-curve-has-composite-order/?answer=75840#post-id-75840Comment by fgrieu for <p>No, there is not.</p>
<p>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.</p>
https://ask.sagemath.org/question/75838/quick-check-that-an-elliptic-curve-has-composite-order/?comment=75848#post-id-75848Thanks. 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.Tue, 06 Feb 2024 19:02:57 +0100https://ask.sagemath.org/question/75838/quick-check-that-an-elliptic-curve-has-composite-order/?comment=75848#post-id-75848