{{{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)
        #walltime(te),walltime(t)
///
(0.086560964584350586, 0.00029110908508300781)
(0.083863019943237305, 0.00052189826965332031)
(0.089411020278930664, 0.00088596343994140625)
(5.7692141532897949, 0.017783880233764648)
(8.648176908493042, 0.030264139175415039)
(9.4172458648681641, 0.056865930557250977)
}}}

{{{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)


R.<t> = PowerSeriesRing(ZZ)
f = 9*t^2+2*t^14+ 7*t^100 +O(t^110)
u = f.valuation_zero_part();u
///
9 + 2*t^12 + 7*t^98 + O(t^108)
}}}

{{{id=11|

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

{{{id=17|

///
}}}

{{{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-function 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/


Asssume:
    - Input-poly is of type ntl_ZZ_pEX
    - squareroot exists (create it by f*f, search for f)
    - assume it is of the form a1*x+... -> no constant term 
Todo find ntl-syntax for the following:
    - polynomial in one variable over finite extension field
    - u = extract coefficient of smallest monomial
    - val = extract smallest exponent
    - s = sqrt(u)
    - a = ? 
    - s = half * (s + a*si) do we also use this function? and what is a?  
///
Traceback (most recent call last):    
  File "", line 1, in <module>
    
  File "/private/var/folders/Yi/YidXnVPxH0WHqC94t6Oxqk+++TI/-Tmp-/tmp9tzYK_/___code___.py", line 4
    in
     ^
SyntaxError: invalid syntax
}}}

{{{id=12|
m=7
c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], m)) 
a = ntl.ZZ_pE([3,2], c)
b = ntl.ZZ_pE([1,2], c)
f = ntl.ZZ_pEX([a, b, b])
f[0]
///
[3 2]
}}}

{{{id=13|
def new_sqrt(self, exponent ,modulus, all=False):
    r""" 
    Compute and return the square root of self (using NTL) modulo m.
    
    INPUT:
      - self - Univariate polynomial with integer coefficients modulo , ntl_ZZ_pEX     
       
      - exponent - Exponent 
       
      - modulus - Modulus, ntl_ZZ_pEX

      - all - bool (default: False); if True, return all square
        roots of self, instead of just one.
    
    ALGORITHM: Newton's method
    
    .. math::
    
       x_{i+1} = \frac{1}{2}( x_i + self/x_i )             

    EXAMPLES::
    """   
            
    val = self.valuation()        
    if val % 2 == 1:
        raise ValueError, "Polynomial does not have a square root since it has odd valuation."
    # compute constant coefficient u and starting point s
    u = self.valuation_zero_part()
    s = u[0].sqrt()
    
    s = a.parent()([s])
    si = invert s
        for cur_prec in sage.misc.misc.newton_method_sizes(prec)[1:]:
            (<PowerSeries>s)._prec = cur_prec
            s = half * (s + a*si)
    
    return s
///
}}}

{{{id=14|
R.<x> = PowerSeriesRing(ZZ,'x',5)
self = (x^2+x)^2
val = self.valuation()        
if val%2==1:
    print 'no root'
a = self.valuation_zero_part() # a is polynomial divided by the degree of the smallest monomial
root=u[0] # first guess of root is coefficient of first non constant term

for i in range(1,100):
    root = 0.5* (root + a/root) 
root;self, val
///
1.00000000000000 + 1.00000000000000*x + O(x^5)
(x^2 + 2*x^3 + x^4, 2)
}}}

{{{id=18|
m=7
c=ntl.ZZ_pEContext(ntl.ZZ_pX([1,1,1], m)) 
a = ntl.ZZ_pE([3,2], c)
b = ntl.ZZ_pE([1,2], c)
f = ntl.ZZ_pEX([a, b, b])
f[0]
///
}}}

{{{id=15|
p=5
b=2
Fq=GF(p^b,'a');
R.<x>=Fq[];
modulus = Fq.modulus()
f=x^2+1
#assume p odd
exponent = (p-1)/2
new_sqrt(f,exponent,modulus)
///
Traceback (most recent call last):    #assume p odd
  File "", line 1, in <module>
    
  File "/private/var/folders/Yi/YidXnVPxH0WHqC94t6Oxqk+++TI/-Tmp-/tmpUPQzmD/___code___.py", line 11, in <module>
    exec compile(u'new_sqrt(f,exponent,modulus)' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/private/var/folders/Yi/YidXnVPxH0WHqC94t6Oxqk+++TI/-Tmp-/tmpFxp0WO/___code___.py", line 30, in new_sqrt
    u = self.valuation_zero_part()
  File "element.pyx", line 306, in sage.structure.element.Element.__getattr__ (sage/structure/element.c:2666)
  File "parent.pyx", line 272, in sage.structure.parent.getattr_from_other_class (sage/structure/parent.c:2840)
  File "parent.pyx", line 170, in sage.structure.parent.raise_attribute_error (sage/structure/parent.c:2611)
AttributeError: 'sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX' object has no attribute 'valuation_zero_part'
}}}

{{{id=16|

///
}}}