from math import sqrt


def discreteOrd(b, m):
    """
    Calculates the size of the multiplicative subgroup generated by b modulo m.
    """
    x = b
    n = 1
    while x != 1:
        x = (x * b) % m
        n += 1
    return n


def isPrimitiveRoot(n, m):
    """
    Determines whether n is a primitive root modulo m.
    """
    return discreteOrd(n, m) == m - 1


def discreteLog(b, n, m):
    """
    Finds k such that b ** k = n modulo m
    """
    k = 1
    n %= m
    p = b
    while p != n:
        k += 1
        p *= b
        p %= m
        if p == b:
            raise ValueError(
                f"The number {n} is not a power of {b} modulo {m}."
            )
    return k


def discretePow(b, k, m):
    """
    Calculates b ** k modulo m using square and multiply.
    """
    result = 1

    while k:
        if k & 1:
            result *= b
            result %= m
        b *= b
        b %= m
        k >>= 1
    return result


if __name__ == "__main__":
    modulo = 20201227

    subjectNum = 7

    # # Example
    # cardPub, doorPub = 5764801, 17807724

    # My input
    cardPub, doorPub = 17773298, 15530095

    cardPriv, doorPriv = map(
        lambda x: discreteLog(subjectNum, x, modulo),
        (cardPub, doorPub)
    )

    print(discretePow(subjectNum, cardPriv * doorPriv, modulo))
