Opened 3 months ago

Closed 3 months ago

#34467 closed defect (fixed)

fix random doctest failure in EllipticCurveHom_velusqrt

Reported by: Lorenz Panny Owned by:
Priority: critical Milestone: sage-9.8
Component: elliptic curves Keywords:
Cc: Antonio Rojas Merged in:
Authors: Lorenz Panny Reviewers: Kwankyu Lee
Report Upstream: N/A Work issues:
Branch: 467eda5 (Commits, GitHub, GitLab) Commit: 467eda55e5ff8ea839cb5cdf06915eb0fc482b9a
Dependencies: Stopgaps:

Status badges


As reported in comment:25:ticket:34303, EllipticCurveHom_velusqrt accidentally computes an irrational isogeny for curves defined over GF(3) with 7 rational points. The reason is that the computation internally requires a point lying outside the kernel, which only in this one specific case will be defined over a cubic instead of a quadratic extension. This in turn implies the linear factors in the numerator of the isogeny won't match up in conjugate pairs, causing the problem.

Quick fix: Simply restrict the implementation to degrees ≥ 9. Since the older EllipticCurveIsogeny implementation is much faster for degrees this small anyway, this restriction won't be a problem for any remotely realistic code.

Change History (8)

comment:1 Changed 3 months ago by Lorenz Panny

Cc: Antonio Rojas added
Status: newneeds_review

comment:2 Changed 3 months ago by Kwankyu Lee

How about adding a doctest for this problematic case with an explanation and a link to this ticket?

comment:3 Changed 3 months ago by git

Commit: 087231256a165b382cea178396daf9e43f1021f8467eda55e5ff8ea839cb5cdf06915eb0fc482b9a

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c71dc3fincrease minimum degree for Îlu formulas to 9
467eda5add failing example

comment:4 Changed 3 months ago by Lorenz Panny


comment:5 Changed 3 months ago by Kwankyu Lee

Reviewers: Kwankyu Lee
Status: needs_reviewpositive_review

Thanks. LGTM.

comment:6 Changed 3 months ago by Frédéric Chapoton

Priority: minorcritical

comment:7 Changed 3 months ago by Matthias Köppe

Milestone: sage-9.7sage-9.8

comment:8 Changed 3 months ago by Volker Braun

Branch: public/increase_velusqrt_minimum_degree_to_9467eda55e5ff8ea839cb5cdf06915eb0fc482b9a
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.