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