def euclid(m, n):
if n == 0:
return m
else:
r = m % n
return euclid(n, r)
def exteuclid(a, b):
r1 = a
r2 = b
s1 = int(1)
s2 = int(0)
t1 = int(0)
t2 = int(1)
while r2 > 0:
q = r1//r2
r = r1-q * r2
r1 = r2
r2 = r
s = s1-q * s2
s1 = s2
s2 = s
t = t1-q * t2
t1 = t2
t2 = t
if t1 < 0:
t1 = t1 % a
return (r1, t1)
p = int(input('Enter 1st prime no. : '))
q = int(input('Enter 2nd prime no. : '))
n = p * q
Pn = (p-1)*(q-1)
key = []
for i in range(2, Pn):
gcd = euclid(Pn, i)
if gcd == 1:
key.append(i)
e = int(5)
r, d = exteuclid(Pn, e)
if r == 1:
d = int(d)
print("d : ", d)
else:
print("Inverse Does not Exist")
M = int(input('Enter M to Encrypt : '))
C = (M**d) % n
print("Encrypted M i.e C : ", C)
N = (C**e) % n
if M == N:
print("Message is Accepted.")
else:
print("Message is not Accepted.")