import random
import math



def isPrime(number):

    # number must be greater than 1
    if (number <= 1):
        return False

    # check if number has no divisor other than itself and 1
    for i in range(2, number):  # int(math.sqrt(number)+1) i > 2 3 4 5 6 7 8 9
        if number % i == 0:
            return False

    return True


# STEP 1: SELECT DIFFERENT PRIME NUMBERS FOR p AND q

# create a list of prime numbers
# pick two prime numbers from the list
primes = [ i for i in range(0, 500) if isPrime(i) ]


p = random.choice(primes)
q = random.choice(primes)

# check that the two numbers are not equal
while p == q:
    q = random.choice(primes)

# STEP 1 ENDS


# STEP 2 MULTIPLY p AND q
n = p*q
# STEP 2 ENDS

# STEP 3 phi = (p-1) x (q-1)
phi = (p-1) * (q-1)
# STEP 3 ENDS


# STEP 4

# set/find gcd
gcd = 2

while gcd != 1:  # when gcd is 1 the two are prime to each other
    e = random.randrange(1, phi)
    gcd = math.gcd(e, phi)
    # set/fnid modulo de % phi

# STEP 4 ENDS

# STEP 5
modDE = 2

while modDE != 1:
    d = random.randrange(1, phi)
    de = d * e
    modDE = de % phi

# STEP 5 ENDS

# print keys
print(f'publicKey: { {e}, {n} }')
print(f'privateKey: { {d}, {n} }')