id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
18589 isogeny efficiency improvement John Cremona "Computation of isogenies of prime degree p is expensive when the degree is neither a ""genus zero"" prime [2,3,5,7,13] or a ""hyperelliptic prime"" [11, 17, 19, 23, 29, 31, 41, 47, 59, 71] (for these there is special code written). In one situation we can save time, after factoring the degree {{{(p^2-1)/2}}} division polynomial, if there is exactly one factor of degree (p-1)/2, or one subset of factors whose product has that degree, then the factor of degree (p-1)/2 must be a kernel polynomial. Then we do not need to check consistency, which is very expensive.
The example which led me to this was with p=89 over a quadratic number field, where E.isogeny_class() was taking days. After the change here that goes down to 3 hours. (There are 4 curves in the isogeny class and the code requires factoring the 89-division polynomial of each!) I used a less extreme example for a doctest: a 37-isogeny." enhancement closed major sage-6.8 elliptic curves fixed isogeny Luca De Feo John Cremona Jeroen Demeyer N/A 3d687e5225f67808eb6c5af5fbf4cb93f2000c62 3d687e5225f67808eb6c5af5fbf4cb93f2000c62