0,0 → 1,53 |
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)) |