Changes between Initial Version and Version 1 of Ticket #18589


Ignore:
Timestamp:
Jun 2, 2015, 7:33:57 PM (8 years ago)
Author:
John Cremona
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #18589 – Description

    initial v1  
    1 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.
     1Computation 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
    33The 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.