fast exponentiation of f
system:sage


{{{id=1|
p=101
b=3
Fq=GF(p^b,'a');
R.<x>=Fq[];
f=x^11+x+1

exponentiating_f(p,b,f)
///
Traceback (most recent call last):    exponentiating_f(p,b,f)
  File "", line 1, in <module>
    
  File "/private/var/folders/Yi/YidXnVPxH0WHqC94t6Oxqk+++TI/-Tmp-/tmpvKtE7k/___code___.py", line 9, in <module>
    exec compile(u'exponentiating_f(p,b,f)' + '\n', '', 'single')
  File "", line 1, in <module>
    
NameError: name 'exponentiating_f' is not defined
}}}

{{{id=2|
def exponentiating_f(p,b,f):

    """
    INPUT:
    
    OUTPUT:
    F = f ^p-1/2
    """
    Fq=GF(p^b,'a');
    R.<x>=Fq[];

    #calculate the frobenius
    frob = R.hom([x^p])
    fp = frob(f)

    #calculate the inverse
    g = Fq.modulus()
    d,fi,v = xgcd(f,R(g))
    #fi is inverse of f modulo g in Fq

    prec = (f.degree() * (p-1)/2) +1
    K.<x> = PowerSeriesRing(Fq, 'x',prec)
    ftmp = K(fp)*K(fi)
   
    F = K(ftmp).square_root()
    return F
///
}}}