search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.41k stars 475 forks source link

Construct isogenies graph in elliptic curves #16942

Open 4a3ae800-1dbb-4954-85d3-ff7abcb5fa55 opened 10 years ago

4a3ae800-1dbb-4954-85d3-ff7abcb5fa55 commented 10 years ago

Let E be an EllipticCurve.

We can not yet construct the graph of the j-invariants of the curves which are isogenous to E. This ticket fills this little gap.

CC: @defeo @JohnCremona @jpflori

Component: elliptic curves

Author: Sébastien Besnier

Branch/Commit: public/ticket/16942 @ 4a943f8

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

4a3ae800-1dbb-4954-85d3-ff7abcb5fa55 commented 10 years ago

New commits:

0d583b4First try to build the volcanoe of an elliptic curve.
777a5c7First draft for isogenies_graph
4a3ae800-1dbb-4954-85d3-ff7abcb5fa55 commented 10 years ago

Branch: u/sbesnier/ticket/16942

4a3ae800-1dbb-4954-85d3-ff7abcb5fa55 commented 10 years ago

Commit: 777a5c7

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

e6f92a6Add some doc tests
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 777a5c7 to e6f92a6

fchapoton commented 10 years ago
comment:3

I have made a cosmetic cleanup of the branch.

But it does not work, test do not pass for me. The doc should say (and the tests should also care) that this is optional, because requiring a database.

New commits:

167a6baMerge branch 'u/sbesnier/ticket/16942' of ssh://trac.sagemath.org:22/sage into 16942
a4740c6trac #16942 cosmetic cleanup
fchapoton commented 10 years ago

Changed branch from u/sbesnier/ticket/16942 to public/ticket/16942

fchapoton commented 10 years ago

Changed commit from e6f92a6 to a4740c6

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from a4740c6 to b4bf82d

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

b4bf82dAdd note about the necessity of having the db_modular_polynomials database.
fchapoton commented 10 years ago
comment:5

Do you want to put this in the state "needs review" ?

4a3ae800-1dbb-4954-85d3-ff7abcb5fa55 commented 10 years ago
comment:6

I thought I did it... Thank you.

fchapoton commented 9 years ago
comment:7

It seems that db_modular_polynomials is not available using sage -i db_modular_polynomials

I think it would be good to explain how to install this database in the doc, if there is some other way.

And AttributeError should be ValueError instead.

And .. note:: should be .. NOTE::

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from b4bf82d to 53fbe4b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

537097fMerge branch 'public/ticket/16942' into 6.5.b4
53fbe4btrac #16942 details
fchapoton commented 9 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
 Let E be an EllipticCurve.  

-We can not yet construct the graph of the j-invariants of the curves which are isougenous to E... This commit fills this little gap.
+We can not yet construct the graph of the j-invariants of the curves which are isogenous to E. This ticket fills this little gap.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

153b354Merge branch 'public/ticket/16942' of trac.sagemath.org:sage into 6.8.rc1
5ebe464trac #16942 no longer depending on database
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 53fbe4b to 5ebe464

fchapoton commented 9 years ago
comment:11

This now does no longer depends on any database.

pjbruin commented 9 years ago
comment:12

Should the method perhaps be renamed isogeny_graph()? I think "isogeny graph" is much more widely used than "isogenies graph" (and Google agrees).

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

e5b72e8changing name
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 5ebe464 to e5b72e8

JohnCremona commented 9 years ago
comment:14

I did not understand the purpose of this ticket from its description, but I do now that I read the code. For elliptic curves over Q and other number fields we have a class for isogeny classes, which has (amongst other methods) a method for displaying the graph. So I wonder whether it might be possible to put this new code under the same umbrella. But that would be more work, so I do not want to delay this.

Certainly "isogeny graph" is a better term.

pjbruin commented 9 years ago
comment:15

I don't have time to really review this now (last working day before my holidays), but why does this return a directed graph? If there is an isogeny in one direction, there always is the dual isogeny in the opposite direction.

JohnCremona commented 9 years ago
comment:16

Good point. And the behaviour for "l = characteristic" should be documented; probably not allowed?

Using the modular polynomial is one way to do it. You could also make use of the existing method E.isogenies_prime_degree(). But in fact as it stands this function is not a method of elliptic curves at all, the input is really just and element j of a finite field. So surely there could be a separate function (not a class method) with input an element of F_q and a prime l, and output a graph on some subset of Fq, and then the elliptic curve class method would call that on its j-invariant.

pjbruin commented 9 years ago
comment:17

Replying to @JohnCremona:

Using the modular polynomial is one way to do it. You could also make use of the existing method E.isogenies_prime_degree(). But in fact as it stands this function is not a method of elliptic curves at all, the input is really just and element j of a finite field. So surely there could be a separate function (not a class method) with input an element of F_q and a prime l, and output a graph on some subset of Fq, and then the elliptic curve class method would call that on its j-invariant.

Actually, the method should perhaps even (optionally?) return the graph of actual elliptic curves instead of the graph of j-invariants. It is likely that the user will want to know exactly which curves over the base field appear in the isogeny graph; if you just have the j-invariants, you only know them up to twist.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from e5b72e8 to ff48452

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

ff48452trac #16942 check that l is not equal to p (characteristic)
fchapoton commented 8 years ago

Changed author from sbesnier to Sébastien Besnier

fchapoton commented 8 years ago
comment:20

I am not really the man to give a positive review, given that I am not an expert.

There seems to remain an issue about directed graph versus undirected graph..

pjbruin commented 8 years ago
comment:21

Replying to @fchapoton:

There seems to remain an issue about directed graph versus undirected graph..

Yes, and it should also be possible to get the actual elliptic curves in the isogeny class, not just their j-invariants (see comment:17). It would probably be a good idea to look at the method EllipticCurve_rational_field.isogeny_graph() and try to keep the interface consistent with that.

JohnCremona commented 8 years ago
comment:23

Replying to @pjbruin:

Replying to @fchapoton:

There seems to remain an issue about directed graph versus undirected graph..

Yes, and it should also be possible to get the actual elliptic curves in the isogeny class, not just their j-invariants (see comment:17). It would probably be a good idea to look at the method EllipticCurve_rational_field.isogeny_graph() and try to keep the interface consistent with that.

Agreed. There will be differences: over number fields isogeny classes are finite; in non-CM cases there is a unique degree of cyclic isogeny between any 2 curves in the class, and the graph we draw uses only those of prime degree which is enough to connect the graph. In CM cases, the situation is very similar to ordinary e.c. over finite fields: isogenies come in 2 types, "horizontal" (between curves whose endomorphism rings are the same order), and "vertical" (between curves whose endo rings are different orders in the same imaginary quadratic field). Vertical isogenies are as before, with a unique cyclic degree; but the horizontal ones do not have unique degrees, in the sense that if two curves hace CM by the same imaginary quadratic order, of discriminant D say, then the set of degrees of isogenies between them is the set of positive integers represented by some binary quadratic form of discriminant D. I toyed with the idea of using the quadratic form as a label for the edges in this case, but in the end went for the smallest prime represented by the form.

Over a finite field, in the ordinary case,the curves in an isogeny class all have the same number of points and their endo rings are all orders in the same i.q.field, and one can again distinguish between horizontal and vertical isogenies. The graph is usually referred to as a "volcano" on account of its shape, where "vertical" and "horizontal" now have physical meaning. If coders are up to the challenge we could have some spectacular isogeny graphs! but getting the layout to look good would be a challenge.

And then there are supersingular curves. Here, for any two isogenous curves, all but finitely many positive integers arise as isogeny degrees between them (see the last chapter of Kohel's thesis), and I don't see any reason for not just showing a complete graph.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from ff48452 to 4a943f8

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

4a943f8Merge branch 'public/ticket/16942' in 8.1.b3
defeo commented 7 years ago
comment:26

Hello. Thanks @fchapoton for taking the time to rebase this.

But, honestly, shouldn't we say this code is not going to be merged?

I am sure there is a lot of interest right now in isogeny graphs over finite fields (because post-quantum crypto, you know), and it would be good if Sage offered some functionality. However this code hardly covers all interesting cases, and it has design issues.

If we could agree on the correct API, I'd be happy to rewrite the code. Let me summarize the issues:

Let me add one more issue: fool-proofness. The size of these graphs is polynomial in the field SIZE! I'm sure a lot of beginners would create a cyptographic-size finite field and then ask for an isogeny graph. This would of course take forever. Maybe we could print a warning when the expected size is too large.

@JohnCremona, @pjbruin, comments?

JohnCremona commented 3 years ago
comment:27

See my comments on #30199.

JohnCremona commented 3 years ago
comment:28

By the way, Sage's optional database of David Kohel's modular polynomials is tiny. Andrew Sutherland has a very much larger database.

defeo commented 3 years ago
comment:29

Maybe we can close this ticket, now that #30199 is going to get in?

Re the modular polynomial database, yes, I had been toying with repackaging it for a while. I hope to be able to finish that work some day...

Maybe it would be good to create a meta-ticket summarizing all wanted functionality regarding isogeny classes and graphs? I can do that if you like.