RSA Two-Key Encryption

So everything in the last seven posts has lead up to this.
The RSA Encryption Algorithm is a mathematical method of generating two encryption keys. You then encrypt a message with one key, and decrypt it using the other key.
This allows you to keep one key private, and publish the other key to the entire world.

Then there are two ways you can use these keys:

1. You look up the public key of your friend, and encrypt a message using their public key. You have guaranteed that no-one can read the message except your friend.
   
2. You encrypt a message using your private key. Everyone can read it, but no-one else but you could have sent it.

So the same technology can be used to keep secrets, and prove identity. Cool.

Euler-Fermat Theory and Prime-testing

As mentioned in the last post, Euler-Fermat's Theory states that for any element m in a group:

$m^{\varphi(n)} = 1 \text{ mod } n$

where $\varphi(n)$ is the totient of n.
The totient of a number is simply the number of Integers that are smaller, and coprime (i.e. no common factors).

This allows us to come up with a simple (though not foolproof) test for prime numbers.
If n is a prime number p, then the number of smaller Integers that are coprime, are all of them. Thus $\varphi(p) = p-1$ for a prime number, and $m^{(p-1)} = 1 \text{ mod } p$ should be true for all the numbers m, smaller than p.