Online credit card security: The RSA algorithm, prime numbers, and Pierre Fermat.

# Prime Numbers and Pierre Fermat Keep Your Secrets Safe Online

Health and Science has moved! You can find new stories here.
The state of the universe.
June 3 2013 5:55 AM

# Prime Numbers Hide Your Secrets

## What happens when you enter your credit card number online?

Prime numbers are all the rage these days. I can tell something’s up when random people start asking me about the randomness of primes—without even knowing that I’m a mathematician! In the past couple of weeks we’ve heard about a beautiful result on the gaps between primes and about cicadas’ prime-numbered life cycles. Our current love affair with primes notwithstanding, many people have wondered whether this is all just abstract theoretical stuff or whether prime numbers have real-world applications.

In fact, they have applications to something as ubiquitous and mundane as making a purchase online. Every time you enter your credit card number on the Internet, prime numbers spring into action. Before your card number is sent over the wires, it must be encrypted for security, and once it’s received by the merchant, it must be decrypted. One of the most common encryption schemes, the RSA algorithm, is based on prime numbers. It uses a “public key,” information that is publicly available, and a “private key,” something that only the decoding party (merchant) has. Roughly speaking, the public key consists of a large number that is the product of two primes, and the private key consists of those two primes themselves. It’s very difficult to factor a given large number into primes. For example, it took researchers two years recently to factor a 232-digit number, even with hundreds of parallel computers. That’s why the RSA algorithm is so effective.

Prime numbers are whole numbers greater than 1 that are not divisible by any whole number other than 1 and itself. The first few are 2, 3, 5, 7, 11, 13 … To explain how the RSA algorithm works, I need to tell you first about something called Fermat’s little theorem. It was discovered by Pierre Fermat, the same French mathematician who came up with the famous Fermat’s last theorem. Fermat had a penchant for being cryptic; in the case of his last theorem, he left a note on the margin of a book stating his theorem and adding: “I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.” Call it the 17th-century version of a Twitter proof. Many professional mathematicians and amateurs tried to reproduce Fermat’s purported proof, and it took more than 350 years to come up with a real one.