{{{id=1|
for i in srange(1,2):
    p=next_prime(10^i)
    for j in srange(2,4):
        b=j
        Fq=GF(p^b,'a');
        R.<x>=Fq[];
        f = x^p - x
        te = walltime()
        exponentiating_f(p,b,f);
        t = walltime()
        f^((p-1)/2);
        print walltime(te),walltime(t)
///
}}}

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

    """
    INPUT:
    - f - Function over F_p^b in x
    - p - Size of the base field
    - b - Degree of the extension of the base field
    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)
    # to compute f^(p-1) use the double slash divisor which does not include a remainder, as there is not one
    ftmp = fp//f
    # compute the square root
    prec = (f.degree() * (p-1)/2) +1
    K.<x> = PowerSeriesRing(Fq, 'x',prec)
    F = K(ftmp).square_root()
    # convert from a power series to a polynomial
    F = F.truncate()
    return F
///
}}}

{{{id=3|

///
}}}

{{{id=4|
for i in srange(1,10):
    p=next_prime(10^i)
    for j in srange(2,10):
        b=j
        Fq=GF(p^b,'a');
        R.<x>=Fq[];
        f = x^p - x
        te = walltime()
        exponentiating_f(p,b,f);
        t = walltime()
        f^((p-1)/2);
        print walltime(te),walltime(t)
///
Traceback (most recent call last):            f = x^p - x
  File "", line 1, in <module>
    
  File "/private/var/folders/Yi/YidXnVPxH0WHqC94t6Oxqk+++TI/-Tmp-/tmpLKQTY0/___code___.py", line 3, in <module>
    exec compile(u"for i in srange(_sage_const_1 ,_sage_const_10 ):\n    p=next_prime(_sage_const_10 **i)\n    for j in srange(_sage_const_2 ,_sage_const_10 ):\n        b=j\n        Fq=GF(p**b,'a');\n        R = Fq['x']; (x,) = R._first_ngens(1);\n        f = x**p - x\n        te = walltime()\n        exponentiating_f(p,b,f);\n        t = walltime()\n        f**((p-_sage_const_1 )/_sage_const_2 );\n        print walltime(te),walltime(t)" + '\n', '', 'single')
  File "", line 9, in <module>
    
NameError: name 'exponentiating_f' is not defined
}}}

{{{id=5|
f^((p-1)/2)
///
x^3 + 3*x^2 + 3*x + 1
}}}

{{{id=6|

///
}}}