The method depends on the fact that while it is easy to calculate the product of two large prime numbers (particularly with the help of a computer) it is, for all practical purposes, impossible to find the factors of a large number if it has only very large prime factors. This is because all methods of finding such factors would take many many thousands of years by even the fastest modern computers.

In order to understand this article you need to know that two numbers are said to be congruent in modulus arithmetic if their difference is divisible by the modulus. For example 23 is congruent to 2 modulus 7 because the difference between 2 and 23 is divisible by 7. Another way of expressing this is to say $a\equiv bmodm$ if and only if $a=pm+b$ where $p$ is an integer. Everything else you need to know is explained in the article.

The Basic Idea
(i) Bob wants to receive a coded message from Alice.
(ii) EVERYBODY knows how to write the message in code.
(iii) Bob is the ONLY person who knows how to decode the coded message.

The idea is that Bob chooses two (very large) prime numbers $p$ and $q$, and then writes $n=pq$. Then $n$ is used to code the message, but $p$ and $q$ are needed to decode the message.

The details:
(1) Bob chooses two very large (distinct) prime numbers $p$ and $q$;
(2) $n=pq$,     $m=\mathrm{lcm}\hspace{0.5em}\{p-1,q-1\}$ (lcm is the least common multiple);
(3) Bob chooses $r$, where $r>1$ and $r$ is coprime with $m$ (i.e. $r$ and $m$ have no factors in common);
(4) Bob then finds the unique $s$ such that $\mathrm{rs}\equiv 1$ mod $m$\.
(5) Bob now tells everyone what $n$ and $r$ are, but does NOT say what $p$, $q$ or $s$ are.
(6) Alice wants to send the message $M$ (a single number) where $M$ and $n$ are coprime and $0<M<n$.
(7) Alice finds $M_c$, where $M_c\equiv M^r$ mod $n$, and sends the message $M_c$ to Bob.
(8) Bob receives the message $M_c$ from Alice and decodes it.

Now Bob knows $p,q,m,n,r,s$, and he uses these to decode the message $M_c$ from Alice so as to find $M$. To do this Bob uses the theorem that $(M_c{)}^s\equiv Mmodn$

In the following example we use small numbers so that you can work through it using a calculator. In practice the numbers would be very big.

An example
(1) Alice wishes to send the message $M$ to Bob
(2) Bob chooses $p=17$, $q=23$; so $n=391$, $m=176$, $r=3$ and $s=59$.
(3) Bob then tells Alice that $n=391$ and $r=3$.
(4) Note: It does not matter how many people have this information, they still won't be able to find $s$.
(5) Alice computes $M_c$ and finds that $M_c=180$.
(5) Bob receives the coded message $180$ from Alice
(6) Bob now calculates $M\equiv {180}^{59}mod391$, and finds Alice's secret message $M$. Can you find it?

In order to find Alice's message you may need some help from the following section.

Working with modulus arithmetic You need to use the following facts:
(1) If $a\equiv bmodn$ then $ac\equiv bcmodn$
(2) If $a\equiv bmodn$ then $a^k\equiv b^{k}modn$.
The proofs of these results are simple.

(1) If $a\equiv bmodn$ then $n$ divides $a-b$ and if $n$ divides $a-b$ then $n$ divides $(a-b)c=ac-bc$ which is the same as saying $ac\equiv bcmodn$.

(2) As $a^k-b^k$ always has a factor $a-b$ for all k it follows that if $n$ divides $a-b$ then $n$ divides $a^k-b^k$ so if $a\equiv bmodn$ then $a^k\equiv b^{k}modn$.

In order to find the secret number that Alice sent to Bob as described above you will need to use the same sort of method as in the following example. Suppose you want to find $x$ where ( $0\le x\le 100$) and ${17}^{13}\equiv xmod101$. As ${17}^{13}$ is too large for most calculators to show exactly we start with ${17}^6=24137569$ and, first dividing this by 101, we find that ${17}^6=(238985)(101)+84$ so we now know that ${17}^6\equiv 84mod101.$ The next step is to use this to tackle ${17}^{13}$.

${\displaystyle \begin{array}{cc}\multicolumn{1}{c}{{17}^{13}}& =({17}^6{)}^2\times 17\\ \multicolumn{1}{c}{}& \equiv {84}^2\times 17\equiv 119952mod101\\ \multicolumn{1}{c}{119952}& =1187\times 101+65\\ \multicolumn{1}{c}{}& \equiv 65mod101.\end{array}}$

Hence $x=65$.

Finally we prove the theorem that $(M_c{)}^s=M^{\mathrm{rs}}\equiv Mmodn$, where $M$ and $n$ are coprime, given that (i) $\mathrm{rs}\equiv 1modm$
(ii) $m=\mathrm{lcm}\hspace{0.5em}[(p-1),(q-1)]$
(iii) $n=\mathrm{pq}$

Proof As $M$ and $n$ are coprime we know that $M$ and $p$ are coprime and $M$ and $q$ are coprime. By Fermat's Little Theorem it follows that

${\displaystyle \begin{array}{cc}\multicolumn{1}{c}{M^{p-1}}& \equiv 1modp\\ \multicolumn{1}{c}{M^{q-1}}& \equiv 1modq\end{array}.}$

Also $(p-1)$ and $(q-1)$ divide $m$ so say $m=j(p-1)=k(q-1)$, then

${\displaystyle M^m={(M^{p-1})}^j\equiv 1^j\equiv 1modp.}$

Similarly

${\displaystyle M^m={(M^{q-1})}^k\equiv 1^k\equiv 1modq.}$

So both $p$ and $q$ divide $M^m-1$ and, as $n=pq$, it follows that $M^m\equiv 1modn$. We know that $\mathrm{rs}\equiv 1modm$ so $\mathrm{rs}=1+\mathrm{mt}$ for some integer $t$. Putting all this together we have

${\displaystyle M^{rs}=(M^1)(M^{mt})\equiv Mmodn.}$

For Further Reading
Singh, Simon (1999) 'The Code Book - The Science of Secrecy from Ancient Egypt to Quantum Cryptography', The Fourth Estate, London ISBN 1 85702 879 1

Flannery, Sarah (2000) 'In Code - A Mathematical Journey' Profile Books, ISBN 1 86197 222 9 This is a unique book, written by a teenager, and highly recommended for all young people interested in mathematics.