opportunistic caching of elliptic-curve and point orders

[yyyyx4]

There are various places in the elliptic-curve code where we could reuse known information about curve and point orders:

• Isogeny codomains (Tate's theorem).
• Base-field extensions.
• Scalar multiplications (Lagrange's theorem).
• Possibly images of points under isogenies, but this is trickier (it requires order_from_multiple in general). It's unclear if this is worthwhile in all cases.

Moreover, EllipticCurvePoint_finite_field currently uses its _order attribute whenever present, but the .order() method fails to actively cache _order after it's been computed. We should also copy over the curve order after computing a point order because it's computed and cached by PARI anyway.

The patch implements items 1-3 of the list and fixes the _order caching in EllipticCurvePoint_finite_field.

CC: @defeo @JohnCremona

Component: elliptic curves

Author: Lorenz Panny

Branch/Commit: a4138a9

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/32786

[yyyyx4]

Branch: public/opportunistic_caching_of_curve_and_point_orders

[yyyyx4]

Commit: 5fbe2b1

[yyyyx4]

Author: Lorenz Panny

[sagetrac-git]

Changed commit from 5fbe2b1 to 792b4c6

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

792b4c6

patchbot dislikes walrus :(

[yyyyx4]

comment:4

Bot is green except for #32737.

[sagetrac-git]

Changed commit from 792b4c6 to 3ae6e85

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3ae6e85

Merge tag '9.5.beta5' into public/opportunistic_caching_of_curve_and_point_orders

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

cd34713

.degree_over() hiccups for a degree-1 extension

[sagetrac-git]

Changed commit from 3ae6e85 to cd34713

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

69db065

move cached-order copying to EllipticCurveIsogeny

[sagetrac-git]

Changed commit from cd34713 to 69db065

[sagetrac-git]

Changed commit from 69db065 to 1474795

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

1474795

oops, update test

[mkoeppe]

comment:9

Stalled in needs_review or needs_info; likely won't make it into Sage 9.5.

[sagetrac-git]

Changed commit from 1474795 to 682dc5a

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

682dc5a

Merge tag '9.5.rc0' into public/opportunistic_caching_of_curve_and_point_orders

[videlec]

comment:11

Member function in PARI/GP does not really exist. They only exist in the gp language. For cypari2, they are only available at C-level not from Python. Some of them are wrapped in cypari2 such as bnf_get_fu. Could you open an issue for cypari2 with the list of member functions that would be desirable to have ? Note that we have a long standing issue about automation sagemath/cypari2#51.

[yyyyx4]

comment:12

That particular comment was about the no member of elliptic curves over finite fields. But it looks like these wrappers provide read-only access (since they return copies), right? To make use of this here we'd need a way of setting the value.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

cd49d25

Merge tag '9.5.rc2' into public/opportunistic_caching_of_curve_and_point_orders

[sagetrac-git]

Changed commit from 682dc5a to cd49d25

[sagetrac-git]

Changed commit from cd49d25 to 366dee1

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

366dee1

Merge tag '9.5' into public/opportunistic_caching_of_curve_and_point_orders

[yyyyx4]

comment:15

In any case, I don't really see a reason to wait with the changes here until cypari2 can do the thing we'd like. This patch already produces huge speedups: For example, one of my scripts (dealing with elliptic curves over a finite field of ~160 bits) runs in 9 seconds after the patch compared to 25 seconds before.

[tscrim]

comment:16

I agree that it would be good to take what we have in hand (since it is worth more than 2 improvements in the bush). My only comment would be why not use a super() call in _acted_upon_ instead of manually building the action and calling that?

[yyyyx4]

comment:17

Sounds reasonable, but I can't get that to work without causing infinite recursions (the superclass ends up calling back into the ._acted_upon_() method we're implementing). Did you have any specific way of doing this in mind?

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:18

Hmm...it seems like the action is implemented in a different way (the base class _acted_upon_() is the trivial one that returns None). Okay then, how about we directly get the action and use that:

Q = self.parent().get_action(ZZ, self_on_left=False)._act_(k, self)

This is more future proof in case a specialized action gets implemented (although it is effectively the same code).

[yyyyx4]

comment:19

Same issue: The .get_action() call rediscovers the method we're currently in (presumably by calling .an_element() on the types first?).

I suppose one thing we could do is to implement ._acted_upon_() in a parent class of EllipticCurvePoint_finite_field and call that directly via super(), without going through the coercion system again. Would you prefer that over the current state of the code?

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

a4138a9

Merge tag '9.6.beta2' into public/opportunistic_caching_of_curve_and_point_orders

[sagetrac-git]

Changed commit from 366dee1 to a4138a9

[tscrim]

comment:21

Right...we are running into this problem because of how the action is implemented (in a very generic way) and this is the first non-generic version. No, this is good. I don't think we need to go to any great lengths for something that might be implemented in the future. Thank you.

[yyyyx4]

comment:22

Great, thank you!

[vbraun]

Changed branch from public/opportunistic_caching_of_curve_and_point_orders to a4138a9