Why are prime numbers so important?

Answer 1

The reason why prime numbers are important practically is because of cryptography.

Prime numbers are an essential part of what is called 'public-key cryptography'.

In this technique two (massively massively large) prime numbers are multiplied together to generate a public key. Meanwhile the identity of exactly which two prime numbers are involved is kept secret (this is the private key).

In the system you can use the public key to encode data and send it to me. But only I can decode that data because only I know the private key.

This only works if prime numbers are involved. Otherwise a third party could come along and just start working out all the divisors of my public key and eventually crack which two (non-prime) numbers are the private key.

When prime numbers are used, the third party can still try this method (called a brute force attack) but would have to try loads more numbers (because my public key only has two divisors - the two prime numbers - which by definition have no divisors of their own). This means that it would take a long time and wouldn't really be worth it.

This technique forms the basis of most encryption over the internet (such as https). A website can send out its public key. The web page can then encode data and send it back to the website but it still can't be deciphered without the private key (even if the public key itself was intercepted).