*how*it works. You pick two primes

`p`and

`q`of roughly the same size. You then let

`n = pq`. This is the modulus you'll use. The public "exponent of encryption"

`e`you set to a small constant (so that people who are sending you messages can do so at little computational cost). Then you find the multiplicative inverse

`d`of

`e`modulo

`phi(n)`where phi(n) is the number of integers less than

`n`to which it is relatively prime. This

`d`is your private key (the "exponent of decryption"). So you publish the pair

`(n,e)`and keep

`d`secret. You can compute

`d`because you know

`p`and

`q`and therefore

`phi(n)`. Other people cannot compute

`d`because they don't know

`p`and

`q`and therefore don't know

`phi(n)`.

Whew. OK. Now for *why* it works:

Fact 1: if x = y mod phi(n) then mNote that you can prove Fact 1 above (the important part of the math, IMHO), using Fermat's Little Theorem or Euler's Theorem.^{x}= m^{y}mod n for all m Fact 2: ed = 1 mod phi(n) because d is selected as e's inverse mod phi(n) Therefore: m^{ed}= m^{1}mod n for all m by fact 1 So when someone encrypts m to you she computes: c = m^{e}mod n When you decrypt you compute: c^{d}= (m^{e})^{d}mod n = m^{ed}mod n by high school math = m^{1}mod n by fact 1 = m mod n And we're done!

This cryptosystem is conjectured to be strong because given `n and e`, there is no known (efficient) algorithm that can find `d`. In fact, if you can find such an algorithm you will be very very *very* famous because then you will have found an efficient way to factor large numbers.