Improve handling of "algorithm" parameter in EllipticCurve_finite_field.cardinality()

[pjbruin]

The following doctest in ell_finite_field.py can fail (by returning a cached result) because the same curve is used in an earlier doctest and may be cached by the UniqueFactory from #11474:

sage: EllipticCurve(GF(10007),[1,2,3,4,5]).cardinality(algorithm='foobar')
Traceback (most recent call last):
...
ValueError: Algorithm is not known

A trivial solution is to use a different curve for this test.

This ticket also makes the handling of the algorithm parameter more consistent and polishes the documentation a bit.

Depends on #11474

CC: @vbraun

Component: elliptic curves

Keywords: elliptic curve cardinality

Author: Peter Bruin, Travis Scrimshaw

Branch/Commit: 545410e

Reviewer: Travis Scrimshaw, Peter Bruin

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

[pjbruin]

Commit: 5251798

[pjbruin]

Branch: u/pbruin/16880-elliptic_curve_cardinality_doctest

[pjbruin]

Changed commit from 5251798 to 654c680

[pjbruin]

Changed branch from u/pbruin/16880-elliptic_curve_cardinality_doctest to u/pbruin/16680-elliptic_curve_cardinality_doctest

[tscrim]

comment:3

Continuing from #16158, the question is should the fact that the value has been computed (and cached) cause a recomputation? Currently how it is implemented is almost no, but it is always recomputed with algorithm='all'.

I'm somewhat inclined to go with what you say, ignore the algorithm keyword always once we have computed the cardinality. (Side point, if we decide to go this route, we should probably switch it to use @cached_method with a key function that ignores the algorithm, but for another ticket.)

However I feel like this could lead to difficult to find bugs, and instead we should recompute everytime a new algorithm is requested. (In this case, we could just convert it to a proper @cached_method.)

[pjbruin]

comment:4

Replying to @tscrim:

Continuing from #16158, the question is should the fact that the value has been computed (and cached) cause a recomputation? Currently how it is implemented is almost no, but it is always recomputed with algorithm='all'.

If all the algorithms are correct, then I see no reason why we should ever recompute the order once it has been computed in any way; it is only useful for debugging purposes.

I'm somewhat inclined to go with what you say, ignore the algorithm keyword always once we have computed the cardinality. (Side point, if we decide to go this route, we should probably switch it to use @cached_method with a key function that ignores the algorithm, but for another ticket.)

However I feel like this could lead to difficult to find bugs, and instead we should recompute everytime a new algorithm is requested. (In this case, we could just convert it to a proper @cached_method.)

I don't have a strong opinion on this, although using @cached_method would have the advantage that we can get rid of manual caching.

[tscrim]

Changed commit from 654c680 to e058079

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:5

Well, we can't get rid of the manual cache because of the cardinality_* methods which set it when called (IMO, these should be private methods and have everything go through cardinality() but I don't have a stake in this).

I've changed it so that algorithm is always ignored if the cardinality is known. If someone wants to check against another algorithm, they can explicitly call one of the cardinality_* methods (which always do the computation).

---

New commits:

0262f93	Merge branch 'u/pbruin/16680-elliptic_curve_cardinality_doctest' of trac.sagemath.org:sage into u/tscrim/16680-elliptic_curve_cardinality_doctest
e058079	Made the cardinality ignore the algorithm if known and added a doctest.

[tscrim]

Changed branch from u/pbruin/16680-elliptic_curve_cardinality_doctest to u/tscrim/elliptic_curve_cardinality-16680

[pjbruin]

comment:6

Replying to @tscrim:

Well, we can't get rid of the manual cache because of the cardinality_* methods which set it when called (IMO, these should be private methods and have everything go through cardinality() but I don't have a stake in this).

I agree; this would be something for another ticket.

I've changed it so that algorithm is always ignored if the cardinality is known. If someone wants to check against another algorithm, they can explicitly call one of the cardinality_* methods (which always do the computation).

Your doctest will probably fail if the elliptic curve is garbage-collected between the two invocations.

[pjbruin]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Peter Bruin

[pjbruin]

Changed commit from e058079 to 545410e

[pjbruin]

Changed author from Peter Bruin to Peter Bruin, Travis Scrimshaw

[pjbruin]

Changed branch from u/tscrim/elliptic_curve_cardinality-16680 to u/pbruin/16680-elliptic_curve_cardinality_doctest

[pjbruin]

comment:7

Replying to @pjbruin:

Your doctest will probably fail if the elliptic curve is garbage-collected between the two invocations.

Fixed this, also polished the documentation a bit more and made heuristic an obsolete synonym for pari. (heuristic just defaulted to pari, so there isn't any real heuristic going on, and "heuristic" may also be misinterpreted as saying that the result is not guaranteed to be correct.)

[pjbruin]

Changed keywords from none to elliptic curve cardinality

[tscrim]

comment:8

Replying to @pjbruin:

Replying to @pjbruin:

Your doctest will probably fail if the elliptic curve is garbage-collected between the two invocations.

Fixed this,

Good point.

also polished the documentation a bit more and made heuristic an obsolete synonym for pari. (heuristic just defaulted to pari, so there isn't any real heuristic going on, and "heuristic" may also be misinterpreted as saying that the result is not guaranteed to be correct.)

I agree since it always went to pari. This also leaves the door open for someone to re-implement this if someone comes up with a proper heuristic. So positive review. Thanks Peter.

[vbraun]

Changed branch from u/pbruin/16680-elliptic_curve_cardinality_doctest to 545410e