Ask Your Question

Early abort for E.cardinality()

asked 2016-06-27 21:38:02 +0200

Vova gravatar image

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 flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted

answered 2018-03-16 13:17:21 +0200

Conrado gravatar image

updated 2018-03-16 15:09:45 +0200

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)

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.

edit flag offensive delete link more

answered 2016-06-28 00:31:28 +0200

tmonteil gravatar image

The code for the cardinality method for elliptic curves can be found on the file src/sage/schemes/elliptic_curves/ (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.

edit flag offensive delete link 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:

However, there is no more file. Do you have any ideas how to do something similar for the most current version of sage (7.2)?

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

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2016-06-27 21:38:02 +0200

Seen: 489 times

Last updated: Mar 16 '18