{{{id=1|
for i in srange(1,10):
    p=next_prime(10^i)
    for j in srange(2,5):
        b=j
        Fq=GF(p^b,'a');
        R.<x>=Fq[];
        f = x^p - x
        te = walltime()
        d=exponentiating_f(p,b,f);
        t = walltime()
        d=f^((p-1)/2)
        print walltime(te),walltime(t)
///
0.0861430168152 0.000305891036987
0.0849678516388 0.000540018081665
0.0920770168304 0.000895977020264
5.86345386505 0.0191268920898
8.66702699661 0.0311658382416
9.26926207542 0.0517730712891
}}}

{{{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
    fp = f(x^p)
    # 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=5|
f^((p-1)/2)
///
x^3 + 3*x^2 + 3*x + 1
}}}

{{{id=6|
p=next_prime(10^2)
b=3
Fq=GF(p^b,'a')
R.<x>=Fq[]
f = x^p - x
%prun d=exponentiating_f(p,b,f)
///
}}}

{{{id=7|
p=5
Fq=GF(5,'a');
R.<x>=Fq[];
f=x^2+1
# calculate the frobenius
fp = f(x^p)
# 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()
F.truncate()

f,K(f).valuation()
R.<t> = PowerSeriesRing(ZZ)
f = 9*t^2+2*t^14+ 7*t^100 +O(t^110)
f,f.valuation(),
#test if f.valuation_zero_part() is invertible (unit = invertible elements of a ring)
u = f.valuation_zero_part();u
u.is_unit()
par=f.parent()
u,
#extract constant term
s=u[0].sqrt()
type(s)
#make s an power series
s=f.parent()([s]);type(s)
///
<type 'sage.rings.power_series_poly.PowerSeries_poly'>
}}}

{{{id=11|

///
x^4 + 2*x^2 + 1
}}}

{{{id=8|
search_src(square_root)
type(F)
///
<type 'sage.rings.power_series_poly.PowerSeries_poly'>
}}}

{{{id=9|
K.<x> = PowerSeriesRing(GF(5,'a'), 'x',prec)

F = K(ftmp).square_root()
///
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_5.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("Sy48eD4gPSBQb3dlclNlcmllc1JpbmcoR0YoNSwnYScpLCAneCcscHJlYykKCkYgPSBLKGZ0bXApLnNxdWFyZV9yb290KCk="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/private/var/folders/Yi/YidXnVPxH0WHqC94t6Oxqk+++TI/-Tmp-/tmphvGT74/___code___.py", line 3, in <module>
    K = PowerSeriesRing(GF(_sage_const_5 ,'a'), 'x',prec, names=('x',)); (x,) = K._first_ngens(1)
NameError: name 'prec' is not defined
}}}

{{{id=10|
sqrt
in
http://localhost:8000/src/rings/power_series_ring_element.pyx/




multiply_and_truncate(self, ntl_ZZ_pEX other, long m)
    and
invert_and_truncate(self, long m)
    in
http://localhost:8000/src/libs/ntl/ntl_ZZ_pEX.pyx/
///
}}}