Opened 8 years ago

Closed 8 years ago

#18611 closed enhancement (fixed)

Further isogeny improvement

Reported by: Jeroen Demeyer Owned by:
Priority: major Milestone: sage-6.8
Component: elliptic curves Keywords:
Cc: John Cremona Merged in:
Authors: Jeroen Demeyer Reviewers: John Cremona
Report Upstream: N/A Work issues:
Branch: 7dfcc8e (Commits, GitHub, GitLab) Commit: 7dfcc8e3a8d27b923afaae87a0b4764008146f5d
Dependencies: #18589 Stopgaps:

Status badges

Description (last modified by Jeroen Demeyer)

To compute all l-isogenies, Sage uses a function mult(f) which computes

gcd( numerator(f(m)), psi )

where m is a rational function giving the multiplication-by-m map (the denominator of m is coprime to psi)

Instead of the above computation, the inverse direction is actually easier to compute: given g, we want to find f such that

gcd( numerator(f(m)), psi ) = g

Using some theory, this is equivalent to

f(m) = 0 mod g

Since f must be irreducible of the same degree as g, this is just the characteristic (= minimal) polynomial of m mod g.


Example timing:

before

sage: %time from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_general; E = EllipticCurve(GF(3^3,'a'), [0,0,0,-1,0]); L = isogenies_prime_degree_general(E, 73)
CPU times: user 1min 52s, sys: 16 ms, total: 1min 52s
Wall time: 1min 52s

after

sage: %time from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_general; E = EllipticCurve(GF(3^3,'a'), [0,0,0,-1,0]); L = isogenies_prime_degree_general(E, 73)
CPU times: user 33.1 s, sys: 107 ms, total: 33.2 s
Wall time: 33.2 s

Change History (12)

comment:1 Changed 8 years ago by Jeroen Demeyer

Dependencies: #18589

comment:2 Changed 8 years ago by Jeroen Demeyer

Description: modified (diff)

comment:3 Changed 8 years ago by Jeroen Demeyer

Description: modified (diff)

comment:4 Changed 8 years ago by Jeroen Demeyer

Branch: u/jdemeyer/ticket/18611

comment:5 Changed 8 years ago by Jeroen Demeyer

Commit: f26e68173ae90f232ca4e3ca744d3285d108ded7
Status: newneeds_review

New commits:

47ccfd5#18589 isogeny improvement
ad56369#18589 simplified code + further improvements
2f83c20#18589: 2 simplifications following review
3d687e5#18589 further one-liner
f26e681Compute inverse of old mult() more efficiently

comment:6 Changed 8 years ago by Jeroen Demeyer

Description: modified (diff)

comment:7 Changed 8 years ago by git

Commit: f26e68173ae90f232ca4e3ca744d3285d108ded77dfcc8e3a8d27b923afaae87a0b4764008146f5d

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

7dfcc8eCompute inverse of old mult() more efficiently

comment:8 Changed 8 years ago by Jeroen Demeyer

Description: modified (diff)

comment:9 Changed 8 years ago by John Cremona

Before I go to look at the code I will confirm the theory sketched in the ticket description. In the notation there, g is irreducible and if alpha is a root of it then the desired f is precisely the min poly of m(alpha).

comment:10 Changed 8 years ago by John Cremona

Reviewers: John Cremona
Status: needs_reviewpositive_review

Looks good and tests out well. For the record:

sage: K.<a>=NumberField(x^2-x-22)                                                              sage: sage: E=EllipticCurve([0,0,1,-1590*a-8580,92750*a+359875])
sage: sage: time E.isogenies_prime_degree(89)
CPU times: user 25min 37s, sys: 2.4 s, total: 25min 39s
Wall time: 25min 37s
[Isogeny of degree 89 from Elliptic Curve defined by y^2 + y = x^3 + (-1590*a-8580)*x + (92750*a+359875) over Number Field in a with defining polynomial x^2 - x - 22 to Elliptic Curve defined by y^2 + y = x^3 + (12594390*a-80556570)*x + (-65385874750*a+319086769867) over Number Field in a with defining polynomial x^2 - x - 22]

though thanks to the code at #18589 this does not use mult() anyway so is not strictly relevant to this ticket.

comment:11 Changed 8 years ago by Jeroen Demeyer

One more remark on the algorithm: the current mult() does not use the fact that the characteristic polynomial is one of finitely many given possibilities. We could probably optimize even more using this information. However, my impression is that it's not currently worth it, since the other parts of the isogeny computation take more time anyway. If you do come across an example where mult() dominates the computation, I'd like to know.

comment:12 Changed 8 years ago by Volker Braun

Branch: u/jdemeyer/ticket/186117dfcc8e3a8d27b923afaae87a0b4764008146f5d
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.