<gh_stars>0
import random

class CryptoMath:
    def __init__(self):
        pass

    @staticmethod
    def modpow(x, p, m):
        return pow(x, p, m)

    @staticmethod
    def is_quadratic_module(x, p):
        ret = CryptoMath. modpow(x, (p-1)//2, p)

        if ret == p - 1:
            ret = -1

        return ret

    @staticmethod
    def modsqrt(a, p):
        if p % 4 == 3:
            return CryptoMath.modpow(a, (p+1)//4, p)

        if p % 8 == 5:
            if CryptoMath.modpow(a, (p-1)//4, p) == 1:
                return CryptoMath.modpow(1, (p+3)//8, p)
            else:
                return (CryptoMath.modpow(2, (p-1)//4, p) * CryptoMath.modpow(a, (p+3)//8, p)) % p

    @staticmethod
    def modsqrt2(a, p):

        # step1
        Q = p - 1
        S = 0
        while Q % 2 == 0:
            S += 1
            Q = Q // 2

        if S == 1:
            return CryptoMath.modpow(a, (p+1)//4, p)

        # step2
        z = 1
        while CryptoMath.is_quadratic_module(z, p) != -1:
            z = random.randint(1, p-1)

        c = CryptoMath.modpow(z, Q, p)

        # step3
        R = CryptoMath.modpow(a, (Q+1)//2, p)
        t = CryptoMath.modpow(a, Q, p)
        M = S

        # step4
        while t != 1:
            i = 0
            t2 = t
            for i in range(1, M):
                t2 = (t2 * t2) % p
                if t2 == 1:
                    break

            b = CryptoMath.modpow(c, 2**(M-i-1), p)
            R = (R * b) % p
            t = (((t * b) % p) * b ) % p
            c = (b * b) % p
            M = i

        return R
        
