Early abort for E.cardinality()

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?

edit retag close merge delete

Sort by » oldest newest most voted

While 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.

more

The code for the cardinality method for elliptic curves can be found on the file 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.

more

It 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/torna...

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)?

( 2016-06-29 14:55:29 +0200 )edit