# This file contains a set of tools for doing RSA encryption.  RSA depends on
# a variation of Fermat's Little Theorem:
#    a ^ ((p - 1) * (q - 1)) = 1 (mod pq) when p and q are prime and (a, p, q)
#                                         are pairwise relatively prime
# We first pick primes p and q, which gives us our modulus (n = p * q).  Then
# we pick values for e (our public key) and d (our private key).  We then
# publish n and e and instruct people to encrypt their messages to us as:
#    encrypted = msg ^ e % n
# where msg is an integer between 0 and (n - 1).  We then decrypt using d:
#    decrypted = encrypted ^ d % n
# We'll find that decrypted = msg.

# returns the prime factors of n as a list
def factors(n):
    m = 2
    result = []
    while m * m <= n:
        if n % m == 0:
            result.append(m)
            n = n / m
        else:
            m += 1
    result.append(n)
    return result

# We start by picking our two primes using factors
# p = ?
# q = ?

# This gives us the modulus
# n = p * q

# Then we pick e and d such that e*d = (p - 1) * (q - 1) * m + 1 for some m.
# We try different values of m and look at factors(temp) for possible values
# for e.
# m = ?
# temp = (p - 1) * (q - 1) * m + 1
# e = ?
# d = temp / e

# We would encrypt this way
# msg = ?
# encrypted = msg ** e % n

# And decrypt this way:
# decrypted = encrypted ** d % n

# returns a^n mod m
def modpow(a, n, m):
        result = 1
        while n > 0:
            result = result * a
            n = n - 1
        return result % m