import math

def modExp(x, y, N):
    if y == 0:
        return 1
    z = modExp(x, y // 2, N)
    if y % 2 == 0:
        return (z * z) % N
    else:
        return (x * z * z) % N


def invModExp(x, N):
    for i in range(1, N):
        val = x * i
        if val % N == 1:
            return i
    return None

def numberOfRelativelyPrime(n):
    count = 0
    collection = []
    for i in range(1, n):
        if math.gcd(i, n) == 1:
            collection.append(i)
            count += 1
    # print(f'Relatively prime with {n}: {collection}')
    return count

def encyrpt(m, e, N):
    """Encrypts a message m using the public key (N, e)
    encrypted message = m^e mod N
    """
    return modExp(m, e, N)

def hack_private_key(N, e):
    """Decrypts a message y without the private key using the public key (N, e)
    """
    for p in range(2, N):
        if (N % p) == 0:
            q = N // p
            d = invModExp(e, (p - 1) * (q - 1))
            return d

def decrypt_message_without_private_key(y, N, e):
    """Decrypts a message y without the private key using the public key (N, e)
    """
    d = hack_private_key(N, e)
    return modExp(y, d, N)


print(f'Q1: {modExp(2, 345, 31)}, {modExp(2, 345, 31) == 2 ** 345 % 31}')
print(f'Q2: {modExp(2, 31, 11)}, {modExp(2, 31, 11) == 2 ** 31 % 11}')
print(f'Q3: {modExp(3, 2003, 5)}, {modExp(3, 2003, 5) == 3 ** 2003 % 5}')
print(f'Q4: {invModExp(13, 22)}')

# Using Fermat's little theorem to get the the initial part where 2^6, 3^6 etc are all congruent to 1 mod 7.
# Then we decompose the initial given problem expression by only leaving the powers that cannot be divided by 6.
# For example 2^20 becomes 2^2 (since the remaining 18 is divisible by 6) and 3^30 becomes 3^0 since 30 is divisible by 6.
print(f'Q5: 6 (derived without coding)') # https://www.math.cmu.edu/~cargue/arml/archive/15-16/number-theory-09-27-15-solutions.pdf

print(f'Q6: {numberOfRelativelyPrime(143)}')
print(f'Q7: {math.gcd(22608, 10206)}')
print(f'Q8: {hack_private_key(133, 7)}') # N=133, e=7
print(f'Q9: {decrypt_message_without_private_key(5, 133, 7)}') # y=5, N=133, e=7
print(f'Q10: {encyrpt(5, 3, 3*11)}') # p=3, q=11, d=7, e=3, m=5