Why are primes important in cryptography?

Question

Most basic and general explanation: cryptography is all about number theory, and all integer numbers (except 0 and 1) are made up of primes, so you deal with primes a lot in number theory.

More specifically, some important cryptographic algorithms such as RSA critically depend on the fact that prime factorization of large numbers takes a long time. Basically you have a "public key" consisting of a product of two large primes used to encrypt a message, and a "secret key" consisting of those two primes used to decrypt the message. You can make the public key public, and everyone can use it to encrypt messages to you, but only you know the prime factors and can decrypt the messages. Everyone else would have to factor the number, which takes too long to be practical, given the current state of the art of number theory.

Simple? Yup.

If you multiply two large prime numbers, you get a huge non-prime number with only two (large) prime factors.

Factoring that number is a non-trivial operation, and that fact is the source of a lot of Cryptographic algorithms. See one-way functions for more information.

Addendum: Just a bit more explanation. The product of the two prime numbers can be used as a public key, while the primes themselves as a private key. Any operation done to data that can only be undone by knowing one of the two factors will be non-trivial to unencrypt.

Here is a very simple and common example.

The RSA encryption algorithm which is commonly used in secure commerce web sites, is based on the fact that it is easy to take two (very large) prime numbers and multiply them, while it is extremely hard to do the opposite - meaning: take a very large number, given which it has only two prime factors, and find them.

It's not so much the prime numbers themselves that are important, but the algorithms that work with primes. In particular, finding the factors of a number (any number).

As you know, any number has at least two factors. Prime numbers have the unique property in that they have exactly two factors: 1 and themselves.

The reason factoring is so important is mathematicians and computer scientists don't know how to factor a number without simply trying every possible combination. That is, first try dividing by 2, then by 3, then by 4, and so forth. If you try to factor a prime number--especially a very large one--you'll have to try (essentially) every possible number between 2 and that large prime number. Even on the fastest computers, it will take years (even centuries) to factor the kinds of prime numbers used in cryptography.

It is the fact that we don't know how to efficiently factor a large number that gives cryptographic algorithms their strength. If, one day, someone figures out how to do it, all the cryptographic algorithms we currently use will become obsolete. This remains an open area of research.

Because nobody knows a fast algorithm to factorize an integer into its prime factors. Yet, it is very easy to check if a set of prime factors multiply to a certain integer.