p = 1234567891
q = 987654323
e = 127
m = 14152019010605


n = p * q
print('n = ', n)

c = (m ** e) % n
print('cyphertext = ', c)

a = p-1
b = q-1
phi = a*b

# extended Euclidian algorithm to find x and y
# for ax + bx = gcd(a,b)
def egcd(a,b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q,r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b

    return x, y

print('x, y = ', egcd(phi,e))


# find greatest common divisor between 2 number
def gcd(a,b):
    while b != 0:
        a, b = b, a % b
    return a

print('gcd = ', gcd(a,b))


# find d, given e and phi
def multiplicative_inverse(e,phi):
    d = 0
    x1 = 0
    x2 = 1
    y1 = 1
    temp_phi = phi

    while e > 0:
        temp1 = temp_phi//e
        temp2 = temp_phi - temp1 * e
        temp_phi = e
        e = temp2

        x = x2 - temp1 * x1
        y = d - temp1 * y1

        x2 = x1
        x1 = x
        d = y1
        y1 = y

        if temp_phi == 1:
            return d + phi

print('d = ', multiplicative_inverse(e,phi))

print('private key is ', multiplicative_inverse(e,phi),',', n)
print('public key is ', e,',',n)