Subversion Repositories Code-Repo

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