Add test to EllipticCurve.isogeny() to check for validity of kernel polynomials

[defeo]

In this example

sage: K = GF(47^2)
sage: E = EllipticCurve([0, K.gen()])
sage: f = E.division_polynomial(7).factor()[4][0]
sage: E.is_supersingular()
True
sage: E.isogeny(f).codomain().is_supersingular()
False
sage: phi = E.isogeny(E.division_polynomial(7).factor()[8][0])
sage: phi(E.random_point())
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
...
TypeError: Coordinates [16*z2 + 30, 3*z2 + 22, 1] do not define a point on Elliptic Curve defined by y^2 = x^3 + (3*z2+36)*x over Finite Field in z2 of size 47^2

The factors of the seventh division polynomial are not detected as bad kernel polynomials, and a wrong isogeny is computed instead.

Tests to detect these cases are in .isogenies_prime_degree_general(). They should be moved to an independent function and called before applying Vélu's formulas.

[cremona]

Remember that the Trace of Frobenius is an integer, not an element of the field, so seeing 94 which is 0 mod 47 is ok. Secondly, you have omitted the isogeny whose kernel is the product of the 3 linear factors of the 7-division polynomial. Thirdly, if you want to see the 7-isogenous curves it is better to do

E.isogenies_prime_degree(7)

since it is non-trivial to combine the factors of the division polynomial correctly. In this case there are only two 7-isogenies. Not that E.isogeny(f) does *not* actually check that f is a valid kernel polynomial even when check=True is give (the default). It should! When it was written we did not have code to do that but now we do. It is slightly buried in the function isogenies_prime_degree_general().

[defeo]

Replying to cremona:

Remember that the Trace of Frobenius is an integer, not an element of the field, so seeing 94 which is 0 mod 47 is ok.

I agree with that, but doesn't Sato-Tate say that two curves are isogenous over a finite field iff they have the same trace? As I said, j=0 and j=36 are isogenous over GF(47²), but the exact curves in the example are not. And, indeed:

sage: phi = E.isogeny(E.division_polynomial(7).factor()[8][0])
sage: phi(E.random_point())
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
...
TypeError: Coordinates [16*z2 + 30, 3*z2 + 22, 1] do not define a point on Elliptic Curve defined by y^2 = x^3 + (3*z2+36)*x over Finite Field in z2 of size 47^2

Secondly, you have omitted the isogeny whose kernel is the product of the 3 linear factors of the 7-division polynomial.

Yes. I just wanted to highlight the bug. One of the buggy factors would have been enough.

Thirdly, if you want to see the 7-isogenous curves it is better to do

E.isogenies_prime_degree(7)

since it is non-trivial to combine the factors of the division polynomial correctly.

Absolutely. However, I found the bug while doing a more general search.

Not that E.isogeny(f) does *not* actually check that f is a valid kernel polynomial even when check=True is give (the default). It should! When it was written we did not have code to do that but now we do. It is slightly buried in the function isogenies_prime_degree_general().

Well, that's not completely correct:

sage: E.isogeny(E.base_field().polynomial_ring().random_element(3))
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...
ValueError: The polynomial does not define a finite subgroup of the elliptic curve.

So there are some checks, but they are buggy, at least for j=0,1728, I suspect.

I do not have time to dig this further right now. Hopefully in a couple of weeks I can come up with a fix.

[cremona]

The j-invariant does not determine the trace since it only determines the curve up to twist; in your case there are more than 2 twists as well.

Yes, some checking is done for validity of kernel polys, but that is misleading since bad input passes those tests as they are not complete.

We'll come back to that.

[cremona]

Can we close this as invalid / won't fix? I just re-read the comments and think that I explained why none of the output which had been thought to be suspect was incorrect.

[defeo]

I still don't get it. Admittedly, E.isogeny(f) does not test that f is a valid kernel polynomial. But, why is f not a valid kernel polynomial in this example:

sage: f = E.division_polynomial(7).factor()[4][0]
sage: E.is_supersingular()
True
sage: E.isogeny(f).codomain().is_supersingular()
False

Also, the TypeError in comment 2 is not nice and would deserve fixing.

[cremona]

The kernel poly of a 7-isogeny is a degree 3 factor of the 7-division poly but not every degree 3 factor is a kernel poly! In this case the 3 roots of your degree 3 factor, which all lie in GF(47^{6), are the x-coordinates of points in 3 different subgroups of order 7.}

In the function isogenies_prime_degree_general() in sage.schemes.elliptic_curves.isogeny_small_degree, this is implemented properly: factor the l-division poly (here l is an odd prime); keep only factors of degree dividing (l-1)/2; for each such factor work out whether or not it is an irreducible factor of a kernel poly.

It would be possible to extract from the code of that function a test for whether a polynomial of degree (l-1)/2 actually is a kernel poly. Feel free to make a ticket for that! The relevent theory is in Kimi Tsukazaki's thesis (cited in that file).

[defeo]

Oh, right!

Can't we just edit this ticket so that it points to the problem, instead of closing it and opening a new one?

[cremona]

Sure, go ahead. Once we have a stand-alone function test_kernel_poly(E,f,ell) it is clear where to put a call to it: in place of lines 2450-2454 where now it only tests if the polynomial divides the division poly. I should have done this ages ago.

[cremona]

Working on it...

[cremona]

New commits:

​0c120af

#23222: check validity of isogeny kernel polynomials

[git]

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

​f7518f7

#23222: fix docstring formatting error

[chapoton]

red banch, needs rebasing

[cremona]

Replying to chapoton:

red branch, needs rebasing

I will rebase it, but it would be good to have a commitment from someone to review it, since the actual work on this was done over 6 months ago.

[git]

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

​0683290

Merge branch 'develop' into 23222

[defeo]

It's been in my todo list for 6 months indeed. But I won't have time before Christmas.

[defeo]

I have one doctest failure:

sage -t --long --warn-long 83.4 src/sage/schemes/elliptic_curves/ell_field.py                                                          
**********************************************************************                                                                 
File "src/sage/schemes/elliptic_curves/ell_field.py", line 1023, in sage.schemes.elliptic_curves.ell_field.EllipticCurve_field.isogeni$
s_prime_degree
Failed example:
    E.isogenies_prime_degree(5)
Exception raised:
    Traceback (most recent call last):
      File "/data/dfl/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 671, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/data/dfl/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1086, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.schemes.elliptic_curves.ell_field.EllipticCurve_field.isogenies_prime_degree[28]>", line 1, in <module>
        E.isogenies_prime_degree(Integer(5))
      File "/data/dfl/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_field.py", line 1091, in isogenies_prime$
degree
        return sum([isogenies_prime_degree(self, d) for d in L], [])
      File "/data/dfl/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/isogeny_small_degree.py", line 2328, in isog$
nies_prime_degree
        return isogenies_prime_degree_general(E,l, minimal_models=minimal_models)
      File "/data/dfl/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/isogeny_small_degree.py", line 2197, in isog$
nies_prime_degree_general
        return [E.isogeny(k) for k in ker]
      File "/data/dfl/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_field.py", line 880, in isogeny
        raise RuntimeError("Unable to construct isogeny: %s" % e)
    RuntimeError: Unable to construct isogeny: 'sage.rings.fraction_field_FpT.FpTElement' object has no attribute 'divides'
**********************************************************************

...investigating.

[defeo]

The doctest failure is due to #27064. No issue to be addressed here.

[defeo]

In is_kernel_polynomial, there is this test:

psi_m = E.division_polynomial(m)
if not f.divides(psi_m):
    return False

isn't it (much) more efficient to do

if E.division_polynomial(m, x=f.parent().quo(f).gen()) != 0:
    return False

[defeo]

The doc still says

   * "check" (default: True) does some partial checks that the

        input is valid (e.g., that the kernel polynomial provided is
        valid); however, invalid input can in some cases still pass,
        since that the points define a group is not checked.

what are the invalid inputs that still pass?

[cremona]

I will correct the docstring and also avoid using f.divides as suggested.

[git]

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

​f123620	Merge branch 'develop' of trac.sagemath.org:sage into 23222
​0c30e53	Merge branch 'develop' into 23222
​7e7593f	#23222 small change to avoid #27064, and update docstring
​72a61bb	Merge remote-tracking branch 'trac/u/cremona/23222' into 23222

[git]

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

​f123620	Merge branch 'develop' of trac.sagemath.org:sage into 23222
​0c30e53	Merge branch 'develop' into 23222
​7e7593f	#23222 small change to avoid #27064, and update docstring
​72a61bb	Merge remote-tracking branch 'trac/u/cremona/23222' into 23222
​28e369f	Merge branch 'u/cremona/23222' of git://trac.sagemath.org/sage into t/23222/23222

[defeo]

Doctests pass. I just fixed a minor problem in the docstring (r""" instead of """). Thanks, and sorry for the long time.

[cremona]

Thanks!

[chapoton]

one py3-incompatible import was added here ; fix at #27107