Cryptographic Algorithm

Algorithm.py

import functools
def gcd(x, y):
    '''
    Euclidean Algorithm
    return gcd(x, y)
    '''
    while y:
        x, y = y, x % y
    return x

def egcd(x, y):
    '''
    Extended Euclidean Algorithm
    return a, b, gcd(x, y) such that ax + by = gcd(x, y)
    '''
    if y == 0:
        return 1, 0, x
    else:
        q = x // y
        r = x % y
        b, a, g = egcd(y, r)
        return a, b - x // y * a, g

def mod_inv(a, n):
    '''
    return b such that ab = 1 mod n
    '''
    inv, _, _ = egcd(a, n)
    return inv % n

def chinese_remainder(eq1, eq2):
    '''
    Chinese remainder theorem
    calculate x such that
        x = a1 mod n1
        x = a2 mod n2

    @param eq1 = (a1, n1)
    @param eq2 = (a2, n2)
    @return x, mod(= n1*n2)
    '''
    a1, n1 = eq1
    a2, n2 = eq2
    p, q, g = egcd(n1, n2)
    x = a1 + (a2 - a1)*p*n1
    mod = n1*n2
    return x % mod, mod

def baby_step_giant_step(g, y, p, q):
    '''
    baby-step giant-step algorithm
    calculate x such that g^x(=y) mod p
    @param g generator
    @param y = g^x
    @param p modulus(prime)
    @param q order of g
    @return x discrete logarithm
    '''
    table = {}
    m = int(q ** 0.5 + 1)

    # baby step
    b = 1
    for j in range(m):
        table[b] = j
        b = b * g % p

    gm = mod_inv(pow(g, m, p), p)

    r = y
    # giant step
    for i in range(m):
        if r in table:
            x = i*m + table[r]
            print("Found:", x)
            return x
        else:
            r = r * gm % p

def pohlig_hellman(p, g, y, phi_p):
    '''
    pohlig hellman algorithm
    '''
    print(phi_p)
    eqs = []
    for q in phi_p:
        b = baby_step_giant_step(pow(g, (p-1)//q, p), pow(y, (p-1)//q, p), p, q)
        eqs.append((b, q))

    x, mod = functools.reduce(chinese_remainder, eqs)
    return x