# 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.

from math import *

# returns a list of the factors of n for n > 0
def factors(n):
    root = int(sqrt(n))
    factors1 = [1]
    factors2 = [n]
    for m in range(2, root + 1):
        if n % m == 0:
            factors1.append(m)
            factors2.insert(0, n / m)
    # special case for perfect squares--root is a factor just once
    if root * root == n:
        factors1.pop()
    return factors1 + factors2

# returns true if n is prime, false if it is not
def isPrime(n):
    return factors(n) == [1, n]

# computes a ^ n mod m
def modpow(a, n, m):
    result = 1
    # loop invariant: result * a^n = (original a) ^ (original n)
    a = a % m
    while (n > 0):
        if n % 2 == 0:
            a = a * a % m
            n = n / 2
        else:
            result = result * a % m
            n = n - 1
    return result

# first pick two primes p and q:
p = 4999
q = 1361

# and then define n as the product of the two primes (our modulus):
n = p * q

# Then we pick e and d such that e*d = k * (p - 1) * (q - 1) + 1 for some k.
# Set up a variable called temp that looks like this:
k = 15
temp = k * (p - 1) * (q - 1) + 1
# check out factors(temp) so that you can choose e and d:
e = 89
d = temp / e

# Now pick a message:
msg = 1234567

# Encrypt it this way:
encrypted = modpow(msg, e, n)

# And decrypt this way:
decrypted = modpow(encrypted, d, n)