The Euler criterion is for n!=0.
I added a fix to deal with the case n==0.
def _sqrt(n, p, sign=0):
""" Generic Tonelli–Shanks algorithm """
if n == 0:
return 0
#check Euler criterion
if pow(n,(p-1)//2,p) != 1:
return None
#compute square root
p_1 = p-1
s = 0
q = p_1
while q & 1 == 0:
q = q>>1
s = s+1
if s == 1:
r = pow(n,(p+1)//4,p)
else:
z = 2
while pow(z,(p-1)//2,p) == 1:
z = z+1
c = pow(z,q,p)
r = pow(n,(q+1)//2,p)
t = pow(n,q,p)
m = s
while True:
if t == 1:
break
else:
for i in range(1,m):
if pow(t,pow(2,i),p) == 1:
break
b = pow(c,pow(2,m-i-1),p)
r = (r*b) %p
t = (t*b*b) %p
c = (b*b) %p
m = i
if sign:
sign = 1
if r&1 != sign:
r = p-r
return r
The Euler criterion is for n!=0. I added a fix to deal with the case n==0.