Changes between Version 1 and Version 2 of Ticket #18589


Ignore:
Timestamp:
06/02/15 19:51:51 (7 years ago)
Author:
cremona
Comment:

New commits:

47ccfd5#18589 isogeny improvement

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #18589

    • Property Status changed from new to needs_review
    • Property Commit changed from to 47ccfd587402b953c612fcd3cddaa541a6847bd3
    • Property Branch changed from to u/cremona/18589
  • Ticket #18589 – Description

    v1 v2  
    11Computation 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.
    22
    3 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 thec ode requires factoring the 89-division polynomial of each!)  I will find a less extreme example for a doctest.
     3The 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.