You are currently browsing the tag archive for the ‘prime factorisation’ tag.

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 p is prime if no other number divides p other than itself and 1. For technical reasons we exclude the number 1 from being prime. So lets see some examples. Is 3 prime? Well, yes, no other number other than 3 and 1 divide it. Is 24 prime? No, because 24 = 12 \times 2.

There is a fundamental theorem in number theory which says that every number n can be uniquely written as a product of prime numbers, i.e. n = p_1^{\alpha_1} \dots p_k^{\alpha_k} where p_1, \dots, p_k are prime. So again, a few examples cannot hurt. Take the number 24. We know that 24 = 12 \times 2, but now 12 is not prime so 12 = 6 \times 2 = 3 \times 2 \times 2. Hence 24 = 3 \times 2 \times 2 \times 2 = 3 \times 2^3. That’s what a prime factorisation is, and what the theorem says is pretty basic, if a number n = 3 \times 2^3, then n = 24.

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.

Read the rest of this entry »