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 º b mod m 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 = lcm {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 rs º 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 º 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 º M mod n

Click to see the proof of this result which is given at the end of this article.

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 º 180⁵⁹ mod 391, 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 º b mod n then ac º bc mod n
(2) If a º b mod n then a^k º b^k mod n.
The proofs of these results are simple.

(1) If a º b mod n 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 º bc mod n.

(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 º b mod n then a^k º b^k mod n.

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 £ x £ 100) and 17¹³ º x mod 101. As 17¹³ is too large for most calculators to show exactly we start with 17⁶=24137569 and, first dividing this by 101, we find that 17⁶=(238985)(101)+84 so we now know that 17⁶ º 84 mod 101. The next step is to use this to tackle 17¹³.

1713 =(176)2 ×17 º 842 ×17 º 119952 mod 101 119952 =1187×101 + 65 º 65 mod 101.

Hence x=65.

Finally we prove the theorem that (M_c)^s = M^rs º M mod n, where M and n are coprime, given that (i) rs º 1 mod m
(ii) m = lcm [(p-1), (q-1)]
(iii) n=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

Mp-1 º 1 mod p Mq-1 º 1 mod q .

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

Mm=(Mp-1)j º 1j º 1 mod p.

Similarly

Mm=(Mq-1)k º 1k º 1 mod q.

So both p and q divide M^m-1 and, as n=pq, it follows that M^m º 1 mod n. We know that rs º 1 mod m so rs=1+mt for some integer t. Putting all this together we have

Mrs=(M1)(Mmt) º M mod n.

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.