Opened 10 years ago

Closed 10 years ago

Last modified 10 years ago

#7907 closed defect (fixed)

Bug in characteristic 2 isogenies of degree >3

Reported by: cremona Owned by: cremona
Priority: major Milestone: sage-4.3.1
Component: elliptic curves Keywords: isogeny
Cc: wuthrich, shumow Merged in: sage-4.3.1.alpha2
Authors: John Cremona Reviewers: Christian Wuthrich
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by cremona)

The method __compute_omega_general() in ell_curve_isogeny.py contains

        for j  in xrange(0,n-1):
            psi_prpr = psi_prpr + \
                binomial(j+2,2)*psi_coeffs[(j+2)]*cur_x_pow
            cur_x_pow = x*cur_x_pow

where the degree of the isogeny is 2*n+1. In degree 3 (the only case doctested) n=1 and the loop is empty. Otherwise there is a run-time error since the name "binomial" has not been imported.

This will be simple to patch, but of course as this indicated that higher degree isogenies in char.2 have not been tested, other issues might arise.

Patch up soon.

Attachments (2)

trac_7906-isogeny.patch (1.8 KB) - added by cremona 10 years ago.
Applies to 4.3.1.alpha1
trac_7907-isogeny.patch (1.8 KB) - added by cremona 10 years ago.
Applies to 4.3.1.alpha1; replaced previous (wrongly named!)

Download all attachments as: .zip

Change History (9)

comment:1 Changed 10 years ago by cremona

  • Description modified (diff)

comment:2 Changed 10 years ago by cremona

Here's an example of the failure which will be put into a doctest in the patch.

Before:

sage: F = GF(128,'a')                                     
sage: a = F.gen()                                         
sage: E = EllipticCurve([1,0,0,0,(a**6+a**4+a**2+a)])     
sage: x = polygen(F)
sage: ker =  (x^6 + (a^6 + a^5 + a^4 + a^3 + a^2 + a)*x^5 + (a^6 + a^5 + a^2 + 1)*x^4 + (a^6 + a^5 + a^4 + a^3 + a^2 + 1)*x^3 + (a^6 + a^3 + a)*x^2 + (a^4 + a^3 + 1)*x + a^5 + a^4 + a) 
sage: E.isogeny(ker)        
Traceback (most recent call last):
...
NameError: global name 'binomial' is not defined

After:

sage: F = GF(128,'a')                                     
sage: a = F.gen()                                         
sage: E = EllipticCurve([1,0,0,0,(a**6+a**4+a**2+a)])     
sage: x = polygen(F)
sage: ker =  (x^6 + (a^6 + a^5 + a^4 + a^3 + a^2 + a)*x^5 + (a^6 + a^5 + a^2 + 1)*x^4 + (a^6 + a^5 + a^4 + a^3 + a^2 + 1)*x^3 + (a^6 + a^3 + a)*x^2 + (a^4 + a^3 + 1)*x + a^5 + a^4 + a)
sage: E.isogeny(ker)                                      
Isogeny of degree 13 from Elliptic Curve defined by y^2 + x*y = x^3 + (a^6+a^4+a^2+a) over Finite Field in a of size 2^7 to Elliptic Curve defined by y^2 + x*y = x^3 + (a^6+a^5+a^4+a^3+a^2+a)*x + (a^5+a^3) over Finite Field in a of size 2^7

Changed 10 years ago by cremona

Applies to 4.3.1.alpha1

Changed 10 years ago by cremona

Applies to 4.3.1.alpha1; replaced previous (wrongly named!)

comment:3 Changed 10 years ago by cremona

  • Status changed from new to needs_review

comment:4 Changed 10 years ago by cremona

  • Authors set to John Cremona
  • Cc wuthrich shumow added

comment:5 Changed 10 years ago by wuthrich

  • Status changed from needs_review to positive_review

fine. it passes all tests.

comment:6 Changed 10 years ago by rlm

  • Merged in set to 4.3.1.alpha2
  • Resolution set to fixed
  • Reviewers set to Christian Wuthrich
  • Status changed from positive_review to closed

comment:7 Changed 10 years ago by mvngu

  • Merged in changed from 4.3.1.alpha2 to sage-4.3.1.alpha2
Note: See TracTickets for help on using tickets.