Opened 10 years ago

Closed 10 years ago

#8248 closed enhancement (fixed)

Small improvement in checking for elliptic curve isogenies

Reported by: cremona Owned by: cremona
Priority: minor Milestone: sage-4.3.3
Component: elliptic curves Keywords: isogenies
Cc: wuthrich Merged in: sage-4.3.3.alpha1
Authors: John Cremona Reviewers: Chris Wuthrich
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:


When an isogeny is constructed from a kernel polynomial, by default (unless check=False) it is checked whether the given kernel polynomial divides the appropriate division polynomial. This is expensive when the degree is large (e.g. 163!).

We provide a small patch which does this checking more efficiently.

The example in the patch which now takes 20s, used to take many minutes.

Attachments (1)

trac_8248-isogeny.patch (1.9 KB) - added by cremona 10 years ago.
Applies to 4.3.2

Download all attachments as: .zip

Change History (4)

Changed 10 years ago by cremona

Applies to 4.3.2

comment:1 Changed 10 years ago by wuthrich

  • Reviewers set to Chris Wuthrich
  • Status changed from new to needs_review

Applies fine to 4.3.3.aplha0. All tests pass. (execpt, which has nothing to do with this patch).

Thanks, John, for this improvement.


comment:2 Changed 10 years ago by wuthrich

  • Status changed from needs_review to positive_review

comment:3 Changed 10 years ago by mvngu

  • Merged in set to sage-4.3.3.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.