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.Fri, 16 Mar 2018 13:17:21 +0100Early abort for E.cardinality()https://ask.sagemath.org/question/33943/early-abort-for-ecardinality/I loop through curves to find one with prime cardinality. In order to speed up the process, it would be convenient to have early abort option, so that whenever some prime factor of cardinality is found, the algorithm skips that curve and goes to the next one. Any suggestions how this can be done?Mon, 27 Jun 2016 21:38:02 +0200https://ask.sagemath.org/question/33943/early-abort-for-ecardinality/Answer by Conrado for <p>I loop through curves to find one with prime cardinality. In order to speed up the process, it would be convenient to have early abort option, so that whenever some prime factor of cardinality is found, the algorithm skips that curve and goes to the next one. Any suggestions how this can be done?</p>
https://ask.sagemath.org/question/33943/early-abort-for-ecardinality/?answer=41580#post-id-41580While the option is not exposed to Sage, you can call it through the Pari interface:
E = EllipticCurve(GF(2^255-19), [0, 486662, 0, 1, 0])
e = gp.ellinit(E.a_invariants(), E.base().order())
order = e.ellsea(tors=2)
print(order)
The documentation for the `tors` parameter:
> When tors is set to a non-zero value, the function returns 0 as soon as it detects that the order has a small prime factor not dividing tors; SEA considers modular polynomials of increasing prime degree ℓ and we return 0 as soon as we hit an ℓ (coprime to tors) dividing #E(𝔽_q).
The development version of Pari also supports checking the order of the twist (by using a negative `tors`), but it has not been released yet (and not integrated with Sage) as I write this.Fri, 16 Mar 2018 13:17:21 +0100https://ask.sagemath.org/question/33943/early-abort-for-ecardinality/?answer=41580#post-id-41580Answer by tmonteil for <p>I loop through curves to find one with prime cardinality. In order to speed up the process, it would be convenient to have early abort option, so that whenever some prime factor of cardinality is found, the algorithm skips that curve and goes to the next one. Any suggestions how this can be done?</p>
https://ask.sagemath.org/question/33943/early-abort-for-ecardinality/?answer=33944#post-id-33944The code for the `cardinality` method for elliptic curves can be found on the file [`src/sage/schemes/elliptic_curves/ell_finite_field.py`](https://git.sagemath.org/sage.git/plain/src/sage/schemes/elliptic_curves/ell_finite_field.py) (you can click to see it). As you can see (search for `def cardinality`), the default implementation is by calling `pari`, so you can have a look to its source code (in the `C` language) and try to make it early-aborting. There is an alternative (probably slower) implementation in Sage, which is called `cardinality_bsgs`, so you can have a look at it and see if you can deduce that the cardinality is not prime before reaching `return self._order` commands.
Tue, 28 Jun 2016 00:31:28 +0200https://ask.sagemath.org/question/33943/early-abort-for-ecardinality/?answer=33944#post-id-33944Comment by Vova for <p>The code for the <code>cardinality</code> method for elliptic curves can be found on the file <a href="https://git.sagemath.org/sage.git/plain/src/sage/schemes/elliptic_curves/ell_finite_field.py"><code>src/sage/schemes/elliptic_curves/ell_finite_field.py</code></a> (you can click to see it). As you can see (search for <code>def cardinality</code>), the default implementation is by calling <code>pari</code>, so you can have a look to its source code (in the <code>C</code> language) and try to make it early-aborting. There is an alternative (probably slower) implementation in Sage, which is called <code>cardinality_bsgs</code>, so you can have a look at it and see if you can deduce that the cardinality is not prime before reaching <code>return self._order</code> commands.</p>
https://ask.sagemath.org/question/33943/early-abort-for-ecardinality/?comment=33960#post-id-33960It seems that earlier version of sage had an option of passing to cardinality function an early abort command.
For example, something like this:
https://www.ma.utexas.edu/users/tornaria/darcs/sage-gt/sage/schemes/elliptic_curves/sea.py
However, there is no more sea.py file.
Do you have any ideas how to do something similar for the most current version of sage (7.2)?Wed, 29 Jun 2016 14:55:29 +0200https://ask.sagemath.org/question/33943/early-abort-for-ecardinality/?comment=33960#post-id-33960