Subversion Repositories Code-Repo

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
219 Kevin 1 
def modular_sqrt(a, p):
2 
    '''Finds the square root x^2 = a (mod p) and returns x'''
3 
    ''' See http://www.math.vt.edu/people/brown/class_homepages/shanks_tonelli.pdf'''
4 
 
5 
    if Jacobi_Symbol(a, p) != 1:
6 
        return 0
7 
    elif a == 0:
8 
        return 0
9 
    elif p == 2:
10 
        return p
11 
    elif p % 4 == 3:
12 
        return (a**((p+1)/4)) % p
13 
 
14 
    s = p - 1
15 
    e = 0
16 
    while s % 2 == 0:
17 
        s /= 2
18 
        e += 1
19 
 
20 
    n = 2
21 
    while Jacobi_Symbol(n, p) != -1:
22 
        n += 1
23 
 
24 
    x = (a**((s+1)/2)) % p
25 
    b = (a**s) % p
26 
    g = (n**s) % p
27 
    r = e
28 
 
29 
    while True:
30 
        t = b
31 
        m = 0
32 
        for m in range(r):
33 
            if t == 1:
34 
                break
35 
            t = (t**2) % p
36 
 
37 
        if m == 0:
38 
            return x
39 
 
40 
        gs = (g**(2 ** (r - m - 1))) % p
41 
        g = (gs * gs) % p
42 
        x = (x * gs) % p
43 
        b = (b * g) % p
44 
        r = m
45 
 
46 
def Jacobi_Symbol(a, p):
47 
    ls = (a**((p - 1) // 2)) % p
48 
    return -1 if ls == p - 1 else ls
49 
 
50 
if __name__ == '__main__':
51 
    print(modular_sqrt(2,113))
52 
    print(modular_sqrt(19,4481))
53 
    print(modular_sqrt(191,1009))