Opened 8 years ago
Closed 8 years ago
#18611 closed enhancement (fixed)
Further isogeny improvement
Reported by:  Jeroen Demeyer  Owned by:  

Priority:  major  Milestone:  sage6.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: 
Description (last modified by )
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 multiplicationbym
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
Dependencies:  → #18589 

comment:2 Changed 8 years ago by
Description:  modified (diff) 

comment:3 Changed 8 years ago by
Description:  modified (diff) 

comment:4 Changed 8 years ago by
Branch:  → u/jdemeyer/ticket/18611 

comment:5 Changed 8 years ago by
Commit:  → f26e68173ae90f232ca4e3ca744d3285d108ded7 

Status:  new → needs_review 
comment:6 Changed 8 years ago by
Description:  modified (diff) 

comment:7 Changed 8 years ago by
Commit:  f26e68173ae90f232ca4e3ca744d3285d108ded7 → 7dfcc8e3a8d27b923afaae87a0b4764008146f5d 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
7dfcc8e  Compute inverse of old mult() more efficiently

comment:8 Changed 8 years ago by
Description:  modified (diff) 

comment:9 Changed 8 years ago by
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
Reviewers:  → John Cremona 

Status:  needs_review → positive_review 
Looks good and tests out well. For the record:
sage: K.<a>=NumberField(x^2x22) sage: sage: E=EllipticCurve([0,0,1,1590*a8580,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*a8580)*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*a80556570)*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
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
Branch:  u/jdemeyer/ticket/18611 → 7dfcc8e3a8d27b923afaae87a0b4764008146f5d 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
#18589 isogeny improvement
#18589 simplified code + further improvements
#18589: 2 simplifications following review
#18589 further oneliner
Compute inverse of old mult() more efficiently