Opened 10 years ago
Last modified 6 years ago
#11095 needs_work enhancement
Add BMSS algorithm for isogenies of elliptic curves
Reported by:  defeo  Owned by:  cremona 

Priority:  minor  Milestone:  sage6.4 
Component:  elliptic curves  Keywords:  isogenies ecc2011 
Cc:  wuthrich, jpflori, pbruin  Merged in:  
Authors:  Luca De Feo  Reviewers:  John Cremona, Marco Streng 
Report Upstream:  N/A  Work issues:  merge conflicts 
Branch:  public/ticket/11095 (Commits)  Commit:  59417df5c944443f91d51d996d1d825f144ab734 
Dependencies:  Stopgaps: 
Description (last modified by )
Add the algorithm by Bostan, Morain, Salvy and Schost for normalized isogenies in characteristic 0 or large enough.
References:
[BMSS08] Alin Bostan, François Morain, Bruno Salvy, and Éric Schost, Fast algorithms for computing isogenies between elliptic curves, Mathematics of Computation 77 (2008), 1755–1778.
Attachments (3)
Change History (51)
comment:1 Changed 10 years ago by
 Cc wuthrich added
comment:2 Changed 10 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:3 Changed 10 years ago by
 Milestone changed from sage4.7 to sage4.7.1
 Reviewers set to John Cremona
 Status changed from needs_review to needs_work
I like this a lot, and it is a good idea to start moving stuff out of the huge isogenies file. I am planning to do the same for the isogenies of small degree code currently the genus 0 prime degrees 2,3,5,7,13 and the others which can occur over Q. Kimi Tsukazaki and I are working on extending that to all the ell for which X_0(ell)^+
has genus 0.
I tested this against 4.7.rc1 and had some doctest failures. I expect these will be easy to fix.
sage t sage/schemes/elliptic_curves/ell_isogeny_char_zero.py // ** nInitExp failed: using Z/2^2 ********************************************************************** File "/home/jec/sage4.7.rc1/devel/sagemain/sage/schemes/elliptic_curves/ell_isogeny_char_zero.py", line 165: sage: isogeny_Stark(E1pr, E2pr, 11) Exception raised: Traceback (most recent call last): File "/home/jec/sagecurrent/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/home/jec/sagecurrent/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/home/jec/sagecurrent/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_2[7]>", line 1, in <module> isogeny_Stark(E1pr, E2pr, Integer(11))###line 165: sage: isogeny_Stark(E1pr, E2pr, 11) NameError: name 'E1pr' is not defined ********************************************************************** File "/home/jec/sage4.7.rc1/devel/sagemain/sage/schemes/elliptic_curves/ell_isogeny_char_zero.py", line 334: sage: kernel = isogeny_BMSS(E1pr, E2pr, 9) Exception raised: Traceback (most recent call last): File "/home/jec/sagecurrent/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/home/jec/sagecurrent/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/home/jec/sagecurrent/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_3[23]>", line 1, in <module> kernel = isogeny_BMSS(E1pr, E2pr, Integer(9))###line 334: sage: kernel = isogeny_BMSS(E1pr, E2pr, 9) NameError: name 'E1pr' is not defined ********************************************************************** File "/home/jec/sage4.7.rc1/devel/sagemain/sage/schemes/elliptic_curves/ell_isogeny_char_zero.py", line 335: sage: kernel Expected: x^8 + 36*x^7 + 95*x^6 + 84*x^4 + 16*x^3 + 70*x^2 + 12*x + 78 Got: x^4 + 14*x^3 + x^2 + 34*x + 21 ********************************************************************** File "/home/jec/sage4.7.rc1/devel/sagemain/sage/schemes/elliptic_curves/ell_isogeny_char_zero.py", line 337: sage: kernel.is_square() Expected: False Got: True ********************************************************************** File "/home/jec/sage4.7.rc1/devel/sagemain/sage/schemes/elliptic_curves/ell_isogeny_char_zero.py", line 339: sage: isogeny_kernel(E1pr, E2pr, 9, algorithm="bmss") Expected: Traceback (most recent call last): ... ValueError: The two curves are not linked by a normalized isogeny of degree 9 Got: Traceback (most recent call last): File "/home/jec/sagecurrent/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/home/jec/sagecurrent/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/home/jec/sagecurrent/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_3[26]>", line 1, in <module> isogeny_kernel(E1pr, E2pr, Integer(9), algorithm="bmss")###line 339: sage: isogeny_kernel(E1pr, E2pr, 9, algorithm="bmss") NameError: name 'E1pr' is not defined ********************************************************************** 2 items had failures: 1 of 22 in __main__.example_2 4 of 28 in __main__.example_3 ***Test Failed*** 5 failures. For whitespace errors, see the file /home/jec/.sage//tmp/.doctest_ell_isogeny_char_zero.py [3.8 s]
comment:4 Changed 10 years ago by
 Status changed from needs_work to needs_review
Ooops! I had made some last minute change to the doctest and must have tested the wrong file afterwards. The new patch passes all tests, including testall long
comment:5 Changed 10 years ago by
 Cc jpflori added
comment:6 Changed 10 years ago by
 Status changed from needs_review to needs_work
I realized that my code for BMSS fails when the isogeny has strictly positive valuation at x, which happens for example when the origin is a point of order 2 and the isogeny has odd degree as in the code below
sage: from sage.schemes.elliptic_curves.ell_isogeny_char_zero import * sage: E = EllipticCurve([1,0]) sage: E2 = EllipticCurve([3^4,0]) sage: E.isogeny(kernel=None, codomain=E2, degree=9) Traceback (most recent call last) ... ValueError: The two curves are not linked by a normalized isogeny of degree 9 sage: isogeny_Stark(E,E2,9) x^8  4*x^6 + 10/3*x^4 + 4/3*x^2 + 1/9 sage: isogeny_BMSS(E,E2,9) x^7  4*x^5 + 10/3*x^3 + 4/3*x
The fix is easy, I hope I'll have time to send a revised patch next week.
Changed 10 years ago by
comment:7 Changed 10 years ago by
 Status changed from needs_work to needs_review
Finally, here's the easy fix! I hope it will be ok now.
comment:8 Changed 10 years ago by
 Reviewers changed from John Cremona to John Cremona, Marco Streng
 Status changed from needs_review to needs_work
On sage 4.7.1.alpha3 with this patch:
sage t long devel/sage/sage/interfaces/ecm.py *** *** Error: TIMED OUT! PROCESS KILLED! *** *** [1800.5 s]
comment:9 followup: ↓ 10 Changed 10 years ago by
Thanks for testing, Marco. This is wierd: I can't seem to reproduce the error; besides, I don't see how the ecm.py module interacts with the elliptic_curve package.
I tested on sage 4.7.1.alpha4 with and without the patch and I have no failure in any case. Does anyone understand what's going on? Can anyone confirm the bug?
comment:10 in reply to: ↑ 9 ; followup: ↓ 11 Changed 10 years ago by
Replying to defeo:
Thanks for testing, Marco. This is wierd: I can't seem to reproduce the error; besides, I don't see how the ecm.py module interacts with the elliptic_curve package.
I tested on sage 4.7.1.alpha4 with and without the patch and I have no failure in any case. Does anyone understand what's going on? Can anyone confirm the bug?
I'll see if I can reproduce it, and will let you know tomorrow.
comment:11 in reply to: ↑ 10 Changed 10 years ago by
 Reviewers changed from John Cremona, Marco Streng to John Cremona
 Status changed from needs_work to needs_review
Replying to mstreng:
I'll see if I can reproduce it, and will let you know tomorrow.
The problem vanished. Sorry for the trouble.
comment:12 Changed 10 years ago by
Added depracation warnings, as suggested by Marco. Apply second patch only (is this going to confuse the patchbot?).
comment:13 followup: ↓ 18 Changed 10 years ago by
 Status changed from needs_review to needs_work
 I'm confused by the
ValueErrors
raised byisogeny_kernel
.
ValueError, "The two curves are not linked by a normalized isogeny of degree %s"%ell
First of all, the comment "or a nonsense polynomial if no such isogeny exists" (line 110) is inconsistent with the documentation of isogeny_BMSS
. Which of the two is correct?
Second, the test "ker_poly.degree() != ell1
" (line 113) implicitly assumes that there is only one possible degree for a normalized isogeny. It would help future developers to have a comment explaining that this is always the case (it is, isn't it?)
Third, why is the test "not check
" there in the Stark case (line 100)? Could isogeny_Stark
return nonsense polynomials just like you say isogeny_BMSS
does? Does a nonsense polynomial always imply that no normalized isogeny exist?
 The word "separable" seems to be missing from the
ValueErrors
 I noticed that (with the default options) the function
isogeny_kernel
will first test if algorithm equals "Stark", "stark", "Starks", or "starks", before detecting that it actually equals "BMSS". It may speed things up by epsilon to put the mostused case first. (this is not the reason for "needs work")
ps. The patch bot seems to have understood that you only want the second patch.
comment:14 followup: ↓ 15 Changed 10 years ago by
Over a finite field theer are always *lots* of isogeny degrees between any two isogenous curves. For ordinary curves the set of degrees is the set of all positive integers represented by a ceratin positive definite quadratic form; for supersingular curves every degree except a finite number are possible (see Kohel's thesis).
comment:15 in reply to: ↑ 14 ; followup: ↓ 16 Changed 10 years ago by
 Reviewers changed from John Cremona to John Cremona, Marco Streng
Replying to cremona:
Over a finite field theer are always *lots* of isogeny degrees between any two isogenous curves.
The word "normalized" is important here. That should limit the possibilities.
comment:16 in reply to: ↑ 15 ; followup: ↓ 17 Changed 10 years ago by
Replying to mstreng:
Replying to cremona:
Over a finite field theer are always *lots* of isogeny degrees between any two isogenous curves.
The word "normalized" is important here. That should limit the possibilities.
Not if you do not mind replacing the codomain with an isomorphic curve, since composing with a scaling map ([u,r,s,t]=[u,0,0,0]) multiplies the constant by u (or maybe u^1
) so u can always be chosen to make the isogeny normalised!
comment:17 in reply to: ↑ 16 Changed 10 years ago by
Replying to cremona:
Not if you do not mind replacing the codomain with an isomorphic curve
I don't mind, but the code in this patch does mind.
comment:18 in reply to: ↑ 13 Changed 10 years ago by
Replying to mstreng:
First of all, the comment "or a nonsense polynomial if no such isogeny exists" (line 110) is inconsistent with the documentation of
isogeny_BMSS
. Which of the two is correct?
I fixed the docs to be more explicit on this, hope it is clear now.
Second, the test "
ker_poly.degree() != ell1
" (line 113) implicitly assumes that there is only one possible degree for a normalized isogeny. It would help future developers to have a comment explaining that this is always the case (it is, isn't it?)
Marco is right: the "normalized" requirement is very strong. Indeed if two isogenies are normalized for the same models, then they are solution to the same differential equation with the same initial conditions. In characteristic 0, this means that their power series expansion at infinity is the same, which I think should be enough to prove that there is only one such isogeny.
In positive characteristic, this means that the power series are equal at least up to the (p1)/2th term (which is the limit up to which the BMSS algorithm can compute the solution). I am less sure about unicity in this case, but I am inclined to think that only one isogeny of degree less than p/4 will satisfy the condition (this is true for multiplicationbym maps, at least).
As an example, take the multiplication maps by 1 and by p1 on a curve E: they are both normalized for the models (E,E), which implies that the expansion at infinity of the multiplicationby(p1) map is x + O(x^{((p1)/2)). Of course the BMSS algorithm will refuse to compute the second map, because it has degree (p1)}2 > p/4.
As a final remark, if we know the right (u,r,s,t) we can normalize the models, as John suggests. But, except for the case of scalar multiplication maps, computing such an isomorphisms is very expensive. I'm working on this in another patch.
Third, why is the test "
not check
" there in the Stark case (line 100)? Couldisogeny_Stark
return nonsense polynomials just like you sayisogeny_BMSS
does? Does a nonsense polynomial always imply that no normalized isogeny exist?
Maybe not, but these algorithms all tend to have some special cases which were not considered in the literature and which yield false answers. So why not test as long as the test comes for free (we have to compute the square root anyway).
 The word "separable" seems to be missing from the
ValueErrors
The constraints on the degree imply that if such an error is returned, then p does not divide ell
(otherwise a ZeroDivisionError
is returned instead), thus no unseparable isogeny of degree ell
exists either.
 I noticed that (with the default options) the function
isogeny_kernel
will first test if algorithm equals "Stark", "stark", "Starks", or "starks", before detecting that it actually equals "BMSS". It may speed things up by epsilon to put the mostused case first. (this is not the reason for "needs work")
done
ps. The patch bot seems to have understood that you only want the second patch.
Yes, but it also used to mention a failure that I was not able to reproduce. It seems to be down now, anyway.
Changed 9 years ago by
comment:19 Changed 9 years ago by
 Description modified (diff)
 Keywords ecc2011 added
what are the work issues for that ticket?
Paul
comment:20 Changed 7 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:21 Changed 7 years ago by
 Description modified (diff)
here is a patch rebased on 5.12.beta4
for the bot :
apply only trac_11095_isogenies_char_0_v3.patch
comment:22 Changed 7 years ago by
apply only trac_11095_isogenies_char_0_v3.patch
Changed 7 years ago by
comment:23 Changed 7 years ago by
apply only trac_11095_isogenies_char_0_v3.patch
comment:24 Changed 7 years ago by
This is going to conflict with #13615  can we agree on an order to do them in?
comment:25 Changed 7 years ago by
 Milestone changed from sage5.12 to sagepending
Oh, definitely #13615 first.
This ticket has been bitrotting for years, although I've never abandoned it and I still use the code from time to time. The new git workflow might be the occasion to go back to it... maybe. In the meantime, I'll put the milestone to sagepending.
comment:26 Changed 7 years ago by
 Cc pbruin added
comment:27 Changed 7 years ago by
 Branch set to u/pbruin/11095isogeny_char_zero
 Commit set to 12d8a9cefc51a11787f77fd8b7e63fc3e1e02723
 Status changed from needs_work to needs_info
I converted the latest patch into a Git branch; there were some conflicts that I hopefully resolved correctly, and all doctests pass.
Would it make sense to call the new module isogeny_char_zero
instead of ell_isogeny_char_zero
? There is also isogeny_small_degree
; it would be nice if we could avoid having modules with three different prefixes (isogeny*
, ell_isogeny*
and ell_curve_isogeny*
)...
comment:28 Changed 7 years ago by
Good point about naming of modules. there are 14 with names starting ell_ in the directory called elliptic_curves and the ell_ prefix could be removed from all of them! (There is also lseries_ell). But doing so would cause a lot of problems for any other branches affecting any of those files...
comment:29 Changed 7 years ago by
 Commit changed from 12d8a9cefc51a11787f77fd8b7e63fc3e1e02723 to 8cae4a71b0836ee6ed2e5607ff3040a0cd538923
Branch pushed to git repo; I updated commit sha1. New commits:
8cae4a7  Trac 11095: rename ell_isogeny_char_zero to isogeny_char_zero

comment:30 Changed 7 years ago by
 Status changed from needs_info to needs_review
Since John and I are for it and nobody seems to be against it, I removed the ell_
prefix from isogeny_char_zero
. (For existing files that would of course be too drastic to do here.)
comment:31 Changed 7 years ago by
Thanks Peter for resurrecting this old ticket of mine. I have no objections to the file renaming.
Back in 2011 Marco Streng and I bypassed Trac and discussed this ticket via mail. I feel I must make an update to explain why the ticket was set to needs work back then.
Essentially, Marco was unhappy about the documentation for two reasons.
 It wasn't clear whether Stark's algorithm could fail silently. I just had a look at it. It can. I'm commiting the necessary modifications to the docs.
 The docstring talks about THE normalized isogeny of degree at most
degree
, but it wasn't immediately clear that this isogeny should be unique. Marco himself gave the proof of unicity. This is explained in the note in the docstring ofisogeny_BMSS
.
I can't find any other issue in my mail logs, so it is good to go for me.
comment:32 Changed 7 years ago by
 Branch changed from u/pbruin/11095isogeny_char_zero to u/defeo/ticket/11095
 Modified changed from 04/26/14 03:03:42 to 04/26/14 03:03:42
comment:33 Changed 7 years ago by
 Commit changed from 8cae4a71b0836ee6ed2e5607ff3040a0cd538923 to 3c978f82831b9b91dfbb6ea675387e4411e7fcb2
 Milestone changed from sagepending to sage6.2
OK. I cannot review it right now, so I just changed the milestone to "undiscourage" people from reviewing it.
New commits:
3c978f8  Modifed docstrings and error messages

comment:34 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:35 Changed 7 years ago by
 Branch changed from u/defeo/ticket/11095 to public/ticket/11095
 Commit changed from 3c978f82831b9b91dfbb6ea675387e4411e7fcb2 to 825710898d20ba257240bd3cbb45f9c194cb6c01
comment:36 Changed 7 years ago by
I've been experimenting a bit and it seems to work well. Would it be possible to make EllipticCurve.isogeny()
and EllipticCurveIsogeny
accept algorithm='bmss'
? In the following example I wanted to compute a 20isogeny between two elliptic curves over a quadratic field (knowing a priori that such an isogeny exists). Trying E.isogeny()
gives a NotImplementedError
and it seems that I have to import isogeny_kernel
:
sage: K.<a> = NumberField(x^2  17*x  120) sage: E = EllipticCurve([0, 1, 0, 89423170640*a + 1999987182576, 87486176701141216*a  1956665490639249900]) sage: E_isog = EllipticCurve([0, 0, 0, 1/3*(6255584200920576*a  139908796923911440), 1/27*(5210907833850999276681216*a + 116544166379886781944583040)]) sage: E.isogeny(kernel=None, codomain=E_isog, degree=20) ... NotImplementedError: For basic Kohel's algorithm, if the kernel degree is even then the kernel must be contained in the two torsion. sage: from sage.schemes.elliptic_curves.isogeny_char_zero import isogeny_kernel sage: isogeny_kernel(E, E_isog, 20) x^10 + (2152280*a + 48136659)*x^9 + (148051244547864/5*a + 3311228950404238/5)*x^8 + (129467694651804753040*a + 2895599965960126731024)*x^7 + (131438756167338709694710304*a + 2939683593714796730731625088)*x^6 + (196151384137228169247793952562368*a  4387008996787386307912516668742368)*x^5 + (211127593344837320952211060140401067136*a  4721958274971357551356075375634080673472)*x^4 + (676089273725371340027412364537916253836377856/5*a + 15121023690506428142245429629695675550575584512/5)*x^3 + (58033791954670621184885097803503676816467494405632*a + 1297950399599077493253508317741911096974395766973184)*x^2 + (26614381917191620756309912883562400685500952121788824576*a  595241952679626281929246822605533328842111805768309632256)*x + 665314371570672918992258944764049661423822960574864980480000*a  14880038428536031844363469294864157021058877011246176591280640
By the way, in this example Stark's algorithm fails; I haven't checked exactly why.
sage: isogeny_kernel(E, E_isog, 20, algorithm='stark') ... RuntimeError: Stark's algorithm returned an unexpected result. Please report this bug.
comment:37 Changed 7 years ago by
 Commit changed from 825710898d20ba257240bd3cbb45f9c194cb6c01 to c7f35aa4654898f3d5e8f4c2b03d6c6d6a8a218a
Branch pushed to git repo; I updated commit sha1. New commits:
c7f35aa  Merge branch 'develop' into ticket/11095isogeny_char_zero

comment:38 Changed 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:39 followup: ↓ 40 Changed 6 years ago by
 Status changed from needs_review to needs_work
 Work issues set to merge conflicts
The merge conflicts appear to result from #11327.
comment:40 in reply to: ↑ 39 ; followup: ↓ 41 Changed 6 years ago by
Replying to pbruin:
The merge conflicts appear to result from #11327.
If so (and it seems likely) I apologise, as the author of #11327, and hope I have not annoyed people. I'll try to remedy that myself to make up for it, but there are several isogenyrelated branches being worked on at the moment and so conflicts are unavoidable.
comment:41 in reply to: ↑ 40 Changed 6 years ago by
Replying to cremona:
Replying to pbruin:
The merge conflicts appear to result from #11327.
If so (and it seems likely) I apologise, as the author of #11327, and hope I have not annoyed people. I'll try to remedy that myself to make up for it, but there are several isogenyrelated branches being worked on at the moment and so conflicts are unavoidable.
I apologise in return: this particular conflict could have been avoided if I had finished my review instead of wondering about adding an extra bit of functionality (comment:36) and leaving it there.
comment:42 Changed 6 years ago by
No big deal. I'm back from conferences+vacation and I'm going to have a look at these conflicts and other isogeny related code in the next few days.
comment:43 Changed 6 years ago by
The conflict seems to me to be not so easy to solve. What do you think ?
comment:44 Changed 6 years ago by
 Commit changed from c7f35aa4654898f3d5e8f4c2b03d6c6d6a8a218a to d88217455f757053cd032671ccfb3688fea5dc31
comment:45 Changed 6 years ago by
For this part of the last commit

src/sage/schemes/elliptic_curves/ell_curve_isogeny.py
a b class EllipticCurveIsogeny(Morphism): 3441 3436 aut = [a for a in auts if a.u == sc] 3442 3437 if len(aut) != 1: 3443 3438 raise ValueError("There is a bug in dual().") 3439 # PROBLEM HERE BELOW IN THE CODE : E0 not defined ! 3444 3440 phi_hat.set_post_isomorphism(WeierstrassIsomorphism(E0,aut[0],E0)) 3445 3441 self.__dual = phi_hat 3446 3442
see #17293, where I also noticed this problem; the correct line is
phi_hat.set_post_isomorphism(aut[0])
comment:46 Changed 6 years ago by
Ok. anyway, the merge I did here was not perfectly clean : the functions moved to isogeny_char_zero are pretty much in their state dating from before #11327
this is rather annoying..
comment:47 Changed 6 years ago by
 Commit changed from d88217455f757053cd032671ccfb3688fea5dc31 to 00f6e5257a4afdfe95f4c33c7c088323d3689ac0
Branch pushed to git repo; I updated commit sha1. New commits:
00f6e52  trac #11095 removed line corrected in another ticket

comment:48 Changed 6 years ago by
 Commit changed from 00f6e5257a4afdfe95f4c33c7c088323d3689ac0 to 59417df5c944443f91d51d996d1d825f144ab734
Branch pushed to git repo; I updated commit sha1. New commits:
59417df  trac #11095 some cleanup in the new file isogeny_char_zero

Besides implementing BMSS, I cleaned a bit
ell_curve_isogeny
, moving the algorithms that do not work in any characteristic to a new moduleell_isogeny_char_zero
. In my view, only theEllipticCurveIsogeny
class and Vélu/Kohel? formulae should remain in ell_curve_isogeny` in the end.BMSS runs significantly faster than Stark's, and works for slightly larger characteristics, I thus set it as the default choice. I haven't produced any serious benchmarks, but I will if the reviewers ask me to.