Add BMSS algorithm for isogenies of elliptic curves #11095

defeo · 2011-03-30T13:33:43Z

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.

Apply: attachment: trac_11095_isogenies_char_0_v3.patch

CC: @categorie @jpflori @pjbruin

Component: elliptic curves

Keywords: isogenies ecc2011

Work Issues: merge conflicts

Author: Luca De Feo

Branch/Commit: public/ticket/11095 @ 59417df

Reviewer: John Cremona, Marco Streng

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

The text was updated successfully, but these errors were encountered:

defeo · 2011-05-03T16:52:46Z

comment:2

Besides implementing BMSS, I cleaned a bit ell_curve_isogeny, moving the algorithms that do not work in any characteristic to a new module ell_isogeny_char_zero. In my view, only the EllipticCurveIsogeny 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.

JohnCremona · 2011-05-03T17:25:17Z

comment:3

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/sage-4.7.rc1/devel/sage-main/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/sage-current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/jec/sage-current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/jec/sage-current/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/sage-4.7.rc1/devel/sage-main/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/sage-current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/jec/sage-current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/jec/sage-current/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/sage-4.7.rc1/devel/sage-main/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/sage-4.7.rc1/devel/sage-main/sage/schemes/elliptic_curves/ell_isogeny_char_zero.py", line 337:
    sage: kernel.is_square()
Expected:
    False
Got:
    True
**********************************************************************
File "/home/jec/sage-4.7.rc1/devel/sage-main/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/sage-current/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/jec/sage-current/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/jec/sage-current/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]

JohnCremona · 2011-05-03T17:25:17Z

Reviewer: John Cremona

defeo · 2011-05-03T19:22:11Z

comment:4

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

defeo · 2011-05-13T13:32:54Z

comment:6

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.

defeo · 2011-06-10T17:58:43Z

comment:7

Attachment: trac_11095_isogenies_char_0.patch.gz

Finally, here's the easy fix! I hope it will be ok now.

mstreng · 2011-07-01T16:49:04Z

comment:8

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]

mstreng · 2011-07-01T16:49:04Z

Changed reviewer from John Cremona to John Cremona, Marco Streng

defeo · 2011-07-06T21:19:12Z

comment:9

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?

mstreng · 2011-07-06T21:23:33Z

comment:10

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.

mstreng · 2011-07-06T21:33:13Z

Changed reviewer from John Cremona, Marco Streng to John Cremona

fchapoton · 2014-05-24T09:26:11Z

Changed commit from 3c978f8 to 8257108

fchapoton · 2014-05-24T09:26:11Z

Changed branch from u/defeo/ticket/11095 to public/ticket/11095

fchapoton · 2014-05-24T09:26:11Z

comment:35

I have made a few minor changes, including:

put new raise statements into python3 syntax
alignement changes in doc

New commits:

`9f71709`	`Merge branch 'u/defeo/ticket/11095' of ssh://trac.sagemath.org:22/sage into 11095`
`8257108`	`trac #11095 minor details (doc formatting and python3 raise syntax)`

pjbruin · 2014-05-24T15:20:38Z

comment:36

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 20-isogeny 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.

sagetrac-git · 2014-05-25T14:16:28Z

Changed commit from 8257108 to c7f35aa

sagetrac-git · 2014-05-25T14:16:28Z

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

`c7f35aa`	`Merge branch 'develop' into ticket/11095-isogeny_char_zero`

pjbruin · 2014-08-22T21:02:23Z

comment:39

The merge conflicts appear to result from #11327.

pjbruin · 2014-08-22T21:02:23Z

Work Issues: merge conflicts

JohnCremona · 2014-08-24T17:41:57Z

comment:40

Replying to @pjbruin:

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 isogeny-related branches being worked on at the moment and so conflicts are unavoidable.

pjbruin · 2014-08-25T13:52:53Z

comment:41

Replying to @JohnCremona:

Replying to @pjbruin:

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 isogeny-related 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.

defeo · 2014-08-25T13:55:53Z

comment:42

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.

fchapoton · 2015-01-27T16:57:01Z

comment:43

The conflict seems to me to be not so easy to solve. What do you think ?

sagetrac-git · 2015-02-09T20:19:07Z

Changed commit from c7f35aa to d882174

sagetrac-git · 2015-02-09T20:19:07Z

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

`c750f70`	`Merge branch 'public/ticket/11095' into 6.5.rc1`
`d882174`	`trac #11095 tentative of rebasing, needs to be checked`

pjbruin · 2015-02-09T20:24:20Z

comment:45

For this part of the last commit

--- a/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py
+++ b/src/sage/schemes/elliptic_curves/ell_curve_isogeny.py
@@ -3441,13 +3436,14 @@ class EllipticCurveIsogeny(Morphism):
 aut = [a for a in auts if a.u == sc]
 if len(aut) != 1:
     raise ValueError("There is a bug in dual().")
+ # PROBLEM HERE BELOW IN THE CODE : E0 not defined !
 phi_hat.set_post_isomorphism(WeierstrassIsomorphism(E0,aut[0],E0))
 self.__dual = phi_hat

see #17293, where I also noticed this problem; the correct line is

phi_hat.set_post_isomorphism(aut[0])

fchapoton · 2015-02-09T20:31:26Z

comment:46

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..

sagetrac-git · 2015-02-09T20:38:56Z

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

`00f6e52`	`trac #11095 removed line corrected in another ticket`

sagetrac-git · 2015-02-09T20:38:56Z

Changed commit from d882174 to 00f6e52

sagetrac-git · 2015-02-11T20:22:15Z

Changed commit from 00f6e52 to 59417df

sagetrac-git · 2015-02-11T20:22:15Z

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

`59417df`	`trac #11095 some cleanup in the new file isogeny_char_zero`

yyyyx4 · 2024-01-08T17:34:34Z

An implementation of the BMSS algorithm was added in #36285.

defeo added this to the sage-4.7 milestone Mar 30, 2011

defeo added c: elliptic curves labels Mar 30, 2011

defeo assigned JohnCremona Mar 30, 2011

This comment has been minimized.

Sign in to view

defeo added the s: needs review label May 3, 2011

JohnCremona modified the milestones: sage-4.7, sage-4.7.1 May 3, 2011

JohnCremona added s: needs work and removed s: needs review labels May 3, 2011

defeo added s: needs review and removed s: needs work labels May 3, 2011

defeo added s: needs work and removed s: needs review labels May 13, 2011

defeo added s: needs review and removed s: needs work labels Jun 10, 2011

mstreng added s: needs work and removed s: needs review labels Jul 1, 2011

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.2, sage-6.3 May 6, 2014

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.3, sage-6.4 Aug 10, 2014

pjbruin added s: needs work and removed s: needs review labels Aug 22, 2014

mkoeppe removed this from the sage-6.4 milestone Dec 29, 2022

yyyyx4 closed this as completed Jan 8, 2024

github-actions bot removed the s: needs work label Jan 8, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add BMSS algorithm for isogenies of elliptic curves #11095

Add BMSS algorithm for isogenies of elliptic curves #11095

defeo commented Mar 30, 2011

This comment has been minimized.

defeo commented May 3, 2011

JohnCremona commented May 3, 2011

JohnCremona commented May 3, 2011

defeo commented May 3, 2011

defeo commented May 13, 2011

defeo commented Jun 10, 2011

mstreng commented Jul 1, 2011

mstreng commented Jul 1, 2011

defeo commented Jul 6, 2011

mstreng commented Jul 6, 2011

mstreng commented Jul 6, 2011

fchapoton commented May 24, 2014

fchapoton commented May 24, 2014

fchapoton commented May 24, 2014

pjbruin commented May 24, 2014

sagetrac-git mannequin commented May 25, 2014

sagetrac-git mannequin commented May 25, 2014

pjbruin commented Aug 22, 2014

pjbruin commented Aug 22, 2014

JohnCremona commented Aug 24, 2014

pjbruin commented Aug 25, 2014

defeo commented Aug 25, 2014

fchapoton commented Jan 27, 2015

sagetrac-git mannequin commented Feb 9, 2015

sagetrac-git mannequin commented Feb 9, 2015

pjbruin commented Feb 9, 2015

fchapoton commented Feb 9, 2015

sagetrac-git mannequin commented Feb 9, 2015

sagetrac-git mannequin commented Feb 9, 2015

sagetrac-git mannequin commented Feb 11, 2015

sagetrac-git mannequin commented Feb 11, 2015

yyyyx4 commented Jan 8, 2024

Add BMSS algorithm for isogenies of elliptic curves #11095

Add BMSS algorithm for isogenies of elliptic curves #11095

Comments

defeo commented Mar 30, 2011

This comment has been minimized.

defeo commented May 3, 2011

JohnCremona commented May 3, 2011

JohnCremona commented May 3, 2011

defeo commented May 3, 2011

defeo commented May 13, 2011

defeo commented Jun 10, 2011

mstreng commented Jul 1, 2011

mstreng commented Jul 1, 2011

defeo commented Jul 6, 2011

mstreng commented Jul 6, 2011

mstreng commented Jul 6, 2011

fchapoton commented May 24, 2014

fchapoton commented May 24, 2014

fchapoton commented May 24, 2014

pjbruin commented May 24, 2014

sagetrac-git mannequin commented May 25, 2014

sagetrac-git mannequin commented May 25, 2014

pjbruin commented Aug 22, 2014

pjbruin commented Aug 22, 2014

JohnCremona commented Aug 24, 2014

pjbruin commented Aug 25, 2014

defeo commented Aug 25, 2014

fchapoton commented Jan 27, 2015

sagetrac-git mannequin commented Feb 9, 2015

sagetrac-git mannequin commented Feb 9, 2015

pjbruin commented Feb 9, 2015

fchapoton commented Feb 9, 2015

sagetrac-git mannequin commented Feb 9, 2015

sagetrac-git mannequin commented Feb 9, 2015

sagetrac-git mannequin commented Feb 11, 2015

sagetrac-git mannequin commented Feb 11, 2015

yyyyx4 commented Jan 8, 2024