Blame | Last modification | View Log | RSS feed
def modular_sqrt(a, p):
'''Finds the square root x^2 = a (mod p) and returns x'''
''' See http://www.math.vt.edu/people/brown/class_homepages/shanks_tonelli.pdf'''
if Jacobi_Symbol(a, p) != 1:
return 0
elif a == 0:
return 0
elif p == 2:
return p
elif p % 4 == 3:
return (a**((p+1)/4)) % p
s = p - 1
e = 0
while s % 2 == 0:
s /= 2
e += 1
n = 2
while Jacobi_Symbol(n, p) != -1:
n += 1
x = (a**((s+1)/2)) % p
b = (a**s) % p
g = (n**s) % p
r = e
while True:
t = b
m = 0
for m in range(r):
if t == 1:
break
t = (t**2) % p
if m == 0:
return x
gs = (g**(2 ** (r - m - 1))) % p
g = (gs * gs) % p
x = (x * gs) % p
b = (b * g) % p
r = m
def Jacobi_Symbol(a, p):
ls = (a**((p - 1) // 2)) % p
return -1 if ls == p - 1 else ls
if __name__ == '__main__':
print(modular_sqrt(2,113))
print(modular_sqrt(19,4481))
print(modular_sqrt(191,1009))