Computing N for Hyperelliptic curve
system:sage


{{{id=1|
def N(E,p,b):
    r"""
    INPUT:
    - 'E' - Hyperelliptic Curve of the form y^2 = f(x)
    - 'p' - a prime number
    - 'b' - q=p^b
    OUTPUT:
    - 'M' The matrix M = (c_(pi-j)), f(x)^((p-1)/2) = \sum c_i x^i
  
  Next step  - 'N' - The matrix N = M M^(p)...M^(p^(g-1)) where M = (c_(pi-j)), f(x)^((p-1)/2) = \sum c_i x^i
    """
    
    #check
    if not p.is_prime():
        return 'p must be prime'
    Fq=GF(p^b,'a');
    C=E.change_ring(Fq)
    f,h = C.hyperelliptic_polynomials()    
    if h != 0:
        return 'E must be of the form y^2 = f(x)'
    d = f.degree()
    if d%2 == 0:
        return 'the degree of f is even'
    g=f.derivative()
    R=g.resultant(f)
    if R == 0:
        return 'f(x) has repeated roots, so it is not smooth'    
    F = f^((p-1)/2)
    #coefficients returns a_0, ... , a_n where f(x) = a_n x^n + ... + a_0
    C = F.list()
    g = E.genus()
    Mall=[]
    for k in range(g):  
        Mk=[];
        a=p^k
        for j in range(1,g+1):
            H=Sequence([(C[i])^a for i in range((p*j-1-g), (p*j-1))])
            H.reverse()
            Mk.append(H);
        Mall.append(matrix(Fq,Mk));
    MS1= MatrixSpace(Fq,g)    
    N = MS1.identity_matrix()
    for l in Mall:
         N=N*l;
    return N;
///
}}}

{{{id=5|
%prun
///
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_4.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("JXBydW4="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/private/var/folders/rt/rtyQ7RPsHRCDmvOBf9SYwU+++TI/-Tmp-/tmpSQXtzF/___code___.py", line 2
    %prun
    ^
SyntaxError: invalid syntax
}}}

{{{id=2|
P.<x>=QQ[];
E=HyperellipticCurve(x^11+x+1,0)
timeit('N(E,103,1)')
///
125 loops, best of 3: 5.75 ms per loop
}}}

{{{id=3|
for E in cremona_curves([10..100]):
    for p in srange(1,1000):        
        for b in srange(1,10):
            print E.label(), p, b, timeit('N(E,p,b)');
///
WARNING: Output truncated!  
<html><a target='_new' href='/home/admin/88/cells/3/full_output.txt' class='file_link'>full_output.txt</a></html>



11a1 1 1 625 loops, best of 3: 10.2 µs per loop
None
11a1 1 2 625 loops, best of 3: 10.2 µs per loop
None
11a1 1 3 625 loops, best of 3: 10.2 µs per loop
None
11a1 1 4 625 loops, best of 3: 10.1 µs per loop
None
11a1 1 5 625 loops, best of 3: 10 µs per loop
None
11a1 1 6 625 loops, best of 3: 10.1 µs per loop
None
11a1 1 7 625 loops, best of 3: 10 µs per loop
None
11a1 1 8 625 loops, best of 3: 10.1 µs per loop
None
11a1 1 9 625 loops, best of 3: 10.1 µs per loop
None
11a1 2 1 625 loops, best of 3: 849 µs per loop
None
11a1 2 2 125 loops, best of 3: 2.05 ms per loop
None
11a1 2 3 125 loops, best of 3: 2.1 ms per loop
None
11a1 2 4 125 loops, best of 3: 2.1 ms per loop
None
11a1 2 5 125 loops, best of 3: 2.17 ms per loop
None
11a1 2 6 125 loops, best of 3: 2.2 ms per loop
None
11a1 2 7 125 loops, best of 3: 2.25 ms per loop
None
11a1 2 8 125 loops, best of 3: 2.33 ms per loop
None
11a1 2 9 125 loops, best of 3: 2.51 ms per loop
None
11a1 3 1 625 loops, best of 3: 856 µs per loop
None
11a1 3 2 125 loops, best of 3: 2.19 ms per loop
None
11a1 3 3 125 loops, best of 3: 2.22 ms per loop
None
11a1 3 4 125 loops, best of 3: 2.26 ms per loop
None
11a1 3 5 125 loops, best of 3: 2.3 ms per loop
None
11a1 3 6 125 loops, best of 3: 2.34 ms per loop
None
11a1 3 7 125 loops, best of 3: 2.37 ms per loop
None
11a1 3 8 125 loops, best of 3: 2.4 ms per loop
None
11a1 3 9 125 loops, best of 3: 2.44 ms per loop
None
11a1 4 1 625 loops, best of 3: 10.7 µs per loop
None
11a1 4 2 625 loops, best of 3: 10 µs per loop
None
11a1 4 3 625 loops, best of 3: 10.1 µs per loop

...

None
11a1 9 4 625 loops, best of 3: 10 µs per loop
None
11a1 9 5 625 loops, best of 3: 10 µs per loop
None
11a1 9 6 625 loops, best of 3: 10 µs per loop
None
11a1 9 7 625 loops, best of 3: 10.1 µs per loop
None
11a1 9 8 625 loops, best of 3: 10.2 µs per loop
None
11a1 9 9 625 loops, best of 3: 10 µs per loop
None
11a1 10 1 625 loops, best of 3: 10 µs per loop
None
11a1 10 2 625 loops, best of 3: 10.1 µs per loop
None
11a1 10 3 625 loops, best of 3: 10 µs per loop
None
11a1 10 4 625 loops, best of 3: 9.98 µs per loop
None
11a1 10 5 625 loops, best of 3: 10 µs per loop
None
11a1 10 6 625 loops, best of 3: 9.99 µs per loop
None
11a1 10 7 625 loops, best of 3: 10 µs per loop
None
11a1 10 8 625 loops, best of 3: 10.1 µs per loop
None
11a1 10 9 625 loops, best of 3: 9.98 µs per loop
None
11a1 11 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_13.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("Zm9yIEUgaW4gY3JlbW9uYV9jdXJ2ZXMoWzEwLi4xMDBdKToKICAgIGZvciBwIGluIHNyYW5nZSgxLDEwMDApOiAgICAgICAgCiAgICAgICAgZm9yIGIgaW4gc3JhbmdlKDEsMTApOgogICAgICAgICAgICBwcmludCBFLmxhYmVsKCksIHAsIGIsIHRpbWVpdCgnTihFLHAsYiknKTs="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/private/var/folders/rt/rtyQ7RPsHRCDmvOBf9SYwU+++TI/-Tmp-/tmpB4viLA/___code___.py", line 3, in <module>
    exec compile(u"for E in cremona_curves((ellipsis_range(_sage_const_10 ,Ellipsis,_sage_const_100 ))):\n    for p in srange(_sage_const_1 ,_sage_const_1000 ):        \n        for b in srange(_sage_const_1 ,_sage_const_10 ):\n            print E.label(), p, b, timeit('N(E,p,b)');" + '\n', '', 'single')
  File "", line 4, in <module>
    
  File "sage_timeit_class.pyx", line 82, in sage.misc.sage_timeit_class.SageTimeit.__call__ (sage/misc/sage_timeit_class.c:696)
  File "sage_timeit_class.pyx", line 59, in sage.misc.sage_timeit_class.SageTimeit.eval (sage/misc/sage_timeit_class.c:557)
  File "/Applications/sage/local/lib/python2.6/site-packages/sage/misc/sage_timeit.py", line 181, in sage_timeit
    if timer.timeit(number) >= 0.2:
  File "/Applications/sage/local/lib/python/timeit.py", line 193, in timeit
    timing = self.inner(it, self.timer)
  File "<magic-timeit>", line 6, in inner
  File "/private/var/folders/rt/rtyQ7RPsHRCDmvOBf9SYwU+++TI/-Tmp-/tmphjoZDq/___code___.py", line 19, in N
    C=E.change_ring(Fq)
  File "/Applications/sage/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_generic.py", line 1278, in base_extend
    return constructor.EllipticCurve([R(a) for a in self.a_invariants()])
  File "/Applications/sage/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/constructor.py", line 331, in EllipticCurve
    return ell_finite_field.EllipticCurve_finite_field(x, y)
  File "/Applications/sage/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_finite_field.py", line 100, in __init__
    EllipticCurve_field.__init__(self, ainvs)
  File "/Applications/sage/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_generic.py", line 164, in __init__
    "Invariants %s define a singular curve."%ainvs
ArithmeticError: Invariants [0, 10, 1, 1, 2] define a singular curve.
}}}

{{{id=4|

///
}}}