Why is the internet safe? (1) RSA and primes.

Ever wonder what happens when you send your card details over the internet? How exactly does public-key encryption work? I will write a brief, non-technical introduction to these concepts and the mathematical background in them, containing some sample code and plenty of examples.

Before we describe the RSA algorithm, there is one important mathematical concept, which is prime numbers and their factorization. Recall that a number is prime if no other number divides other than itself and . For technical reasons we exclude the number from being prime. So lets see some examples. Is prime? Well, yes, no other number other than and divide it. Is prime? No, because .

There is a fundamental theorem in number theory which says that every number can be uniquely written as a product of prime numbers, i.e. where are prime. So again, a few examples cannot hurt. Take the number . We know that , but now is not prime so . Hence . That’s what a prime factorisation is, and what the theorem says is pretty basic, if a number , then .

At this point now I can state what is the fundamental idea behind RSA:

Factoring a number into prime factors is much harder than checking if a number is prime!

But why is this true? There are technical reasons for this but I prefer to think along the following lines. Computers are much like humans, so imagine if a human is given the task of factorising numbers and checking if numbers are prime.