#7096 closed defect (fixed)
bug in dual isogeny computation
Reported by: | cremona | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-4.2.1 |
Component: | elliptic curves | Keywords: | elliptic curve isogeny |
Cc: | shumow@… | Merged in: | sage-4.2.1.alpha0 |
Authors: | Chris Wuthrich | Reviewers: | John Cremona |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
sage: p = 1019 sage: F = GF(p) sage: E = EllipticCurve(F,[1,-1,0,1,1]) sage: psi = E.division_polynomial(7).factor()[3][0] sage: phi = E.isogeny(kernel=psi) sage: assert phi.degree()==7 sage: phi.dual() --------------------------------------------------------------------------- ValueError Traceback (most recent call last) /home/jec/.sage/temp/selmer/14232/_home_jec__sage_init_sage_0.py in <module>() /home/jec/sage-4.1.2.rc0/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_curve_isogeny.pyc in dual(self) 2998 2999 phi_hat.set_pre_isomorphism(pre_isom) -> 3000 phi_hat.set_post_isomorphism(post_isom) 3001 3002 self.__dual = phi_hat /home/jec/sage-4.1.2.rc0/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_curve_isogeny.pyc in set_post_isomorphism(self, postWI) 2627 2628 if (self.__E2 != WIdom): -> 2629 raise ValueError, "Invalid parameter: isomorphism must have domain curve equal to this isogenies'codomain." 2630 2631 if (None == self.__post_isomorphism): ValueError: Invalid parameter: isomorphism must have domain curve equal to this isogenies' codomain.
This looks like something which should be easy to fix.
One month of hard work later: first impressions were deceptive!
Attachments (4)
Change History (25)
comment:1 Changed 10 years ago by
- Owner changed from davidloeffler to (none)
comment:2 Changed 10 years ago by
comment:3 Changed 10 years ago by
Yet another, bigger problem with dual() : Say E -> E' is an isogeny of degree d, then all the algorithm does is creating an isogeny E' -> E of degree d. This does not guarantee that it is the dual; it could be the dual composed with an automorphism, like [-1]. This probably happens quite often as it uses WeierstrassIsomorphism(E,E')
. This returns one of the isomorphisms without any control of it, hence often the sign will be wrong.
The function dual definitely needs a lot of work.
Now, the actual bug reported in this ticket is not in dual but occurs as
E1 = EllipticCurve(GF(1013),[1,-1,0,288,19]) E2 = EllipticCurve(GF(1013),[7,970,0,363,464]) EllipticCurveIsogeny(E1,None,E2,7)
comment:4 Changed 10 years ago by
- Cc shumow@… added
Of course the field in the previous lines should be 1019. The output is
Isogeny of degree 7 from Elliptic Curve defined by y^2 + x*y = x^3 + 1018*x^2 + 288*x + 19 over Finite Field of size 1019 to Elliptic Curve defined by y^2 + 7*x*y + 850*y = x^3 + 970*x^2 + 445*x + 202 over Finite Field of size 1019
which has visibly the wrong, but an isomorphic codomain. After 1 hour of chasing through the code, I was not able to find the error. I include the author as CC in the hope that he might have an idea.
comment:5 Changed 10 years ago by
I worked on the bugs for isogenies and I found two. They should be corrected with the above patch. But I have to do some more work and test it carefully, before it is ready for a review.
comment:6 Changed 10 years ago by
I started implementing some more related to this ticket. Especially the formal()
for isogeny. Then there are two ideas how to compute the dual.
- I can take the implementation as it is now. This yields a isogeny of the correct degree
in the opposite direction. Then I can compute the leading term of the composition in the
formal expansion (or simply check to what multiple the differential is pulled-back to). This
gives me the
WeierstrassIsomorphism
to use. I am not 100 % sure if this will work in all cases. Say the elliptic curve is defined over a finite field and has a cyclic isogeny of degree n2 to itself. It is certain that our current implementation gives back a cyclic isogeny and not just [n]. I fear one could find counterexamples... I have to do some testings. - Otherwise, I will try to implement the full computation of the dual via the formal group. I
believe that there is an algorithm with running time O(n) for an isogeny of prime degree
n. Though I have not checked this in details. It would only involve to compute the first
2n coefficients in [n] and the
division_polynomial
in the formal expansion. The one example I have computed so far by hand was a failure :(. One obstacle here will be the fact that.reversion()
is only defined for power-series with coefficients in Q.
à suivre.
comment:7 Changed 10 years ago by
I found another issue with isogenies.
E = EllipticCurve('11a1') E2 = EllipticCurve('11a2') E2.isogeny(None,codomain=E1,degree=5)
fails with
ValueError: Codomain parameter must be isomorphic to computed codomain isogeny
while E.isogeny(None,codomain=E2,degree=5)
works fine. The reason is that the algorithm for computing the kernel polynomial in compute_isogeny_starks
is only valid for normalised isogenies.
Stark's algorithm is implemented in ell_curve_isogeny.py from scratch and so it contains the computation of the formal expansion of the Weierstrass p function. I wonder if we should add as another possible algorithm to do the same sort of computation, but using the already existing code for formal groups instead. ....
comment:8 Changed 10 years ago by
Yet another bug with dual
. I have to chase that. It does not look like being related to the previously reported bugs.
k = GF(103) E = EllipticCurve(k,[1,0,0,1,-1]) P = E(60,85) phi = E.isogeny(P) phi.dual()
gives
IndexError: list index out of range
in line 3789.
(I keep on adding these bugs here and I try to resolve as many as I can with the patch for this. Only then I will open new tickets for the remaining ones)
comment:9 Changed 10 years ago by
Thanks for your work on this. Perhaps we should make dual raise a NotImplementedError? since it fails in so many different ways?
I think that when Dan Shumow implemented all the isogeny stuff he was mainly interested in certain kinds of isogenies (over finite fields?) so did not test as much in other situations. Just guessing. [For example, he added the model parameter on my request, over Q only; I would have made that the default over Q.]
comment:10 Changed 10 years ago by
The problem is that most errors go back to problems for the EllipticCurveIsogeny
constructor itself. So they can be recreated without dual
. Of course, I don't want isogeny()
to raise a NotImplementedError
. But I will include warnings in the documentation...
comment:11 Changed 10 years ago by
OK. Here we go. That is a patch for this ticket that I would like to be reviewed.
I explain all the changes it introduces as it is quite a long and complicated patch. (I like the fact that the initial comment on the ticket was "This looks like something which should be easy to fix." while it took me a month of quite hard work.)
- I moved the computation of the weierstrass p-function into a seperate file ell_wp.py. I also completely clean it. It used to contain a lot of functions on power series that are already implemented in sage. There is an option now to call the pari version.
- I added a
weierstrass_p
to ell_field.py. - Having redone all the weierstrass_p with laurent and power series rather than with
polynomials, also got rid of the
IndexError
mentioned above. - The dual is now correct and not just up to an automorphism.
- When trying to give an isogeny with a codomain, it now checks if the algorithm fails (typically because there is no cyclic normalized isogeny of this degree). This eliminates a bad bug that was known in the code.
- We can now take duals of non-normalized isogenies
- There is a new function
formal
that computes the formal expansion of the isogeny. - This
formal
can be used to check if the isogeny is normalized; this simplifies and corrects the previous code (which is still there but deprecated). - I included a check to forbid
dual
of isogenies of degree divisible by the charactersitic. - I updated a lot of the documentation of isogenies.
- And I also changed the starting documentation of ell_generic.py to clarify what we mean by an elliptic curve in sage.
There is still a lot that should be done about isogenies for elliptic curves. I hope this patch corrects and clarifies what is possible right now. For further things that one could wish for in sage concerning isogenies and endomorphisms I opened ticket #7368 as a follow up.
Note that this ticket also includes the correction asked for in #7307.
Changed 10 years ago by
patch for this ticket exported against 4.2.alpha1. (in particular after #6886). This patch should be reviewed while the previously submitted should be ignored.
comment:12 Changed 10 years ago by
- Status changed from new to needs_review
comment:13 Changed 10 years ago by
- Status changed from needs_review to needs_work
Sorry I saw that the patch does not include the new file ell_wp.py.
comment:14 Changed 10 years ago by
- Description modified (diff)
You have done a great job, and I look forward to studying it in detail. Unfortunately other work prevents me from doing so for quite a while, so although I was the one who posted this (complete with under-estimation of the work involved) I would be very happy if someone else interested reviews it first.
comment:15 Changed 10 years ago by
- Status changed from needs_work to needs_review
comment:16 Changed 10 years ago by
After writing the above I went ahead anyway and read the patch -- when ell_wp.py is added too I'll try test to test it as well.
comment:17 Changed 10 years ago by
Ok that was easy. now it should be review-able.
comment:18 Changed 10 years ago by
- Status changed from needs_review to positive_review
OK, I relented and have reviewed the patch. It is great. It applies fine to 4.2 and builds and tests ok. (Even better, my not-yet-complete patch for #6887 applied OK on top of this, so a large piece of work which uses isogenies a lot still works fine; that is a very good test, I think). I also built and read through the documentation, which is good -- better than before in several respects. I may have spotted a typo or too but did not note them down so will not delay things by hunting them down.
Positive review: and gives me a spur to finish #6887.
comment:19 Changed 10 years ago by
That was quick ! Thanks a lot.
Chris.
comment:20 Changed 10 years ago by
- Merged in set to sage-4.2.1.alpha0
- Resolution set to fixed
- Reviewers set to John Cremona
- Status changed from positive_review to closed
comment:21 Changed 3 years ago by
- Report Upstream set to N/A
While looking at the code of
{dual()
, I found a second bug in thisgives a ZeroDivisionError?. Only separable isogenies are implented, so one can not possibly take the dual of this separable isogeny of degree 7 in chracteristic 7. A quick check should be introduced here.