sqroot.py

import sys

def sqroot_modulo(x,y):
    p=0;
    for i in range (y-1):
        if(((i*i)%y)==x):
            p=i
            break
    
    return p;

def tonelli_shanks(n, p):
    if n % p == 0:
        return 0
    if pow(n, (p - 1) // 2, p) != 1:
        raise ValueError("n is not a quadratic residue modulo p")
    
    # Step 1: Find Q and S such that p - 1 = Q * 2^S
    Q, S = p - 1, 0
    while Q % 2 == 0:
        Q //= 2
        S += 1
    
    # Step 2: Find a quadratic non-residue (z) modulo p
    z = 2
    while pow(z, (p - 1) // 2, p) != p - 1:
        z += 1
    
    # Step 3: Initialize variables
    M, c, t, r = S, pow(z, Q, p), pow(n, Q, p), pow(n, (Q + 1) // 2, p)
    
    # Step 4: Loop until we find a square root
    while True:
        if t == 0:
            return 0  # n is a quadratic residue, and its square root is 0
        if t == 1:
            return r  # n is a quadratic residue, and its square root is r
        
        # Find the smallest i such that t^(2^i) = 1
        i = 0
        temp = t
        while temp != 1:
            temp = pow(temp, 2, p)
            i += 1
        
        # Calculate b, M, c, and t for the next iteration
        b = pow(c, 2**(M - i - 1), p)
        M = i
        c = pow(b, 2, p)
        t = (t * c) % p
        r = (r * b) % p


a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
x=tonelli_shanks(a,p)
#print(x)
#print(p-x)
a = 288260533169915
p = 1007621497415251