Why are mathematicians so intrigued with prime numbers?

[NobleSavage]

And a second question, I understand they are used in cryptography, but how?

 

[beero1000]

They're the building blocks of numbers, so they're important. But mostly it's because we're pattern junkies, and primes have an intriguing mix of both pattern and chaos. This is actually one reason why they're useful in cryptography - they're random enough to be hard to guess from the outside, but structured enough to be easy to compute from the inside.

A simple example for cryptography: Alice and Bob want to figure out a secret number X that they will both know, but no one else will. However, their discussions about figuring out X will be open to eavesdropping so they need to be careful (i.e. Alice can't just blurt out "Our number should be X!"). So they need a secret way to convey information so that even if someone has full access to their messages, the eavesdropper still won't be able to figure out X (or, at least, the time it takes to work out X is excessively long).

So here's one procedure (this technique is called  Diffie-Hellman):

1. Alice decides on a secret number A. Bob decides on a secret number B. They keep these numbers completely private and don't tell anyone.
2. Alice announces a number P and a number Q.
3. Alice announces the number C which is the remainder of Q^A when divided by P.
4. Bob announces the number D which is the remainder of Q^B when divided by P.
5. Alice computes X, which is the remainder of D^A when divided by P.
6. Bob computes X, which is the remainder of C^B when divided by P.

The two numbers Alice and Bob compute in steps 5 and 6 are the same (essentially because (Q^A)^B = (Q^B)^A), so they have their secret number. On the other hand, because an eavesdropper only knows P, Q, C, and D, they will have to figure out some way to work out X. This is where primes come in, as we want to use their nice properties to say that the eavesdropper will have a difficult time of computing X. If the P that Alice chose was a large prime, and the Q that Alice chose has a nice property that has to do with the primality of P, then figuring out X from P, Q, C, and D is a notoriously hard problem, known as the  discrete logarithm problem. A bunch of cryptographic techniques rely on the (unproved) fact that solving the discrete logarithm problem is intractably difficult, so on average an eavesdropper will probably have to spend time that's exponential the size of P. Since it's reasonably easy to come up with really big primes, and computing X without knowing A or B is unreasonable for really big primes, it's easy to make computing X too costly for an eavesdropper to attempt.

 

[NobleSavage]

Thanks, I'm familiar with the process of public key cryptography, but I never knew the why. I guess the discrete logarithm problem was the idea behind the movie Sneakers. Some mathematician figured out a way to make encryption worthless (they were fuzzy on the details) and the rest was your typical government espionage drama with Robert Redford as a good guy.

 

[bilby]

I like steak; but I prefer prime steak.
Realtors like real estate; but they prefer prime real estate.
Politicians like being ministers; but they prefer to be prime minister.
Mathematicians like numbers; but, obviously, they prefer prime numbers.

Simples.

 

[Malintent]

Thanks, I'm familiar with the process of public key cryptography, but I never knew the why. I guess the discrete logarithm problem was the idea behind the movie Sneakers. Some mathematician figured out a way to make encryption worthless (they were fuzzy on the details) and the rest was your typical government espionage drama with Robert Redford as a good guy.

The "why this works well" is based on the fact that it is trivaily easy to multiply two numbers togther.. even if they are gigantic numbers (hundreds of digits long). That is the Encryption part.

What is nearly impossible to do, is take the super-gigantic number that is the product of two prime numbers, and determine what those two prime numbers are. That is the strenght of the encryption.

If you know one of the prime numbers (because one of those numbers is "yours", because the data was encrypted for only you to read). It is trivially easy to divide the product by your prime number to reveal the other prime number. That is decryption.

Fast encryption / decryption through simple multiply / divide operation. Strong encryption due to the mathamatical difficulty determining the two prime factors of a gigantic number.

 

[Emily Lake]

Aside from the cryptographic approach, primes are cool because they're not part of anything else. They're atoms. All the other numbers break down, like molecules being broken down into their constituent atoms. But primes don't break down. They're the building blocks.

In addition to that, if you lay out all of the integers in any pattern you want, then cross out all of the non-primes, the remaining primes almost, but not quite, make a pattern of their own. Since humans are nearly OCD when it comes to patterns, they fascinate us, trying to see the almost-pattern that isn't there, and trying to understand the formula-that-isn't that underlies them.

 

[NobleSavage]

Aside from the cryptographic approach, primes are cool because they're not part of anything else. They're atoms. All the other numbers break down, like molecules being broken down into their constituent atoms. But primes don't break down. They're the building blocks.

In addition to that, if you lay out all of the integers in any pattern you want, then cross out all of the non-primes, the remaining primes almost, but not quite, make a pattern of their own. Since humans are nearly OCD when it comes to patterns, they fascinate us, trying to see the almost-pattern that isn't there, and trying to understand the formula-that-isn't that underlies them.

You have a link to any of these "almost-patterns" represented visually?

 

[bilby]

Aside from the cryptographic approach, primes are cool because they're not part of anything else. They're atoms. All the other numbers break down, like molecules being broken down into their constituent atoms. But primes don't break down. They're the building blocks.

In addition to that, if you lay out all of the integers in any pattern you want, then cross out all of the non-primes, the remaining primes almost, but not quite, make a pattern of their own. Since humans are nearly OCD when it comes to patterns, they fascinate us, trying to see the almost-pattern that isn't there, and trying to understand the formula-that-isn't that underlies them.

You have a link to any of these "almost-patterns" represented visually?

The numbers 1 - 2,500 represented in a 50 x 50 square grid, with primes shown in red.

 

[beero1000]

Now that I have a little time, I figure I'd expand a little on the technical conditions I alluded to in my description of Diffie-Hellman.

The idea is based on the  multiplicative group of integers modulo n. In particular, we want the group modulo a large prime P. Since P is prime, it is relatively prime to all of the numbers 1, 2, 3, ..., P-1 and so these numbers are all elements of the group. For the group multiplication, we can think of multiplying the numbers and taking remainders after dividing by P. So, for example, if P = 13, then we have 3*5 = 2, because 3*5 = 15 = 13 + 2. Similarly, 6*10 = 4*13 + 8 = 8, and 7*2 = 13 + 1 = 1. This is a  group because the standard multiplication axioms still hold with this type of multiplication. You can even divide, and say that because 7*2 = 1, then 7 = 1/2.

Since P is prime, the group has P - 1 elements, which is basically the most you can hope for in this situation. If we had used a composite number N, we'd have to remove any numbers not relatively prime to N and we'd have a group smaller than N - 1. The bigger the group, the harder it will be to crack the encryption, so using large primes is important here.

Now the idea is to pick a base Q and look at the powers of Q, Q², Q³, ....  Fermat's little theorem implies that for any Q, Q^P = Q, so we know that the powers cycle through a fixed list of values (but we don't know how long the cycle is) and the cycle length divides P - 1. We'd like to pick a Q so that the cycle of powers is as long as possible because if Q cycles quickly, it is easier to figure out the secret number X. A number Q with the property that the cycle is maximally long (length P - 1) is called a  primitive root modulo P. This is a good option to use (another possibility is using a large  Schnorr group).

We can work out the cycles for various Q's relative to 13.
1: 1 immediately repeats.
2: 2 - 4 - 8 - 3 - 6 - 12 - 11 - 9 - 5 - 10 - 7 - 1 - 2 is a primitive root of 13.
3: 3 - 9 - 1 - 3 is not a primitive root
4: 4 - 3 - 12 - 9 - 10 - 1 - 4 is not a primitive root.
etc.

We want to pick a number like 2 for Q. It would be particularly bad to pick a number like 3 (or, even worse, 1). Suppose Alice's secret number is A = 8 and Bob's is B = 10.

If Q = 3, Alice announces 3⁸ -> C = 9, and Bob announces 3¹⁰ -> D = 3. Then, Bob computes 9¹⁰ = X = 9 and Alice computes 3⁸ = X = 9. Thus, Alice and Bob have determined their shared number X = 9. An eavesdropper who knows P = 13, Q = 3, C = 9, and D = 3 can try to brute force the number X by taking powers of Q until they find C or D. So an eavesdropper would try Q¹ = 3, note that D = 3, take B = 1 and compute 9¹ = X = 9. That wasn't a coincidence, and is a bad bad situation. Since 3 has a cycle of length 3, a brute force approach only needs to check Q, Q², and Q³ before finding C and/or D. Then raising the other to the appropriate power yields X.

On the other hand, if Q = 2, Alice announces 2⁸ -> C = 9, and Bob announces 2¹⁰ = 10. Then, Bob computes 9¹⁰ = X = 9 and Alice computes 10⁸ = X = 9. They have determined their shared number X. An eavesdropper who knows P = 13, Q = 2, C = 9, and D = 10 can try to brute force again, but this time, they end up checking 2, 2² = 4, 2³ = 8, ..., 2⁸ = 9 = C before finding C or D and computing X.

For very large numbers P, Q, A, and B, an eavesdropper is almost always forced to compute a huge number of powers before they can expect to find a power that yields C or D. This makes cracking the encryption intractable.

- - - Updated - - -

Aside from the cryptographic approach, primes are cool because they're not part of anything else. They're atoms. All the other numbers break down, like molecules being broken down into their constituent atoms. But primes don't break down. They're the building blocks.

In addition to that, if you lay out all of the integers in any pattern you want, then cross out all of the non-primes, the remaining primes almost, but not quite, make a pattern of their own. Since humans are nearly OCD when it comes to patterns, they fascinate us, trying to see the almost-pattern that isn't there, and trying to understand the formula-that-isn't that underlies them.

You have a link to any of these "almost-patterns" represented visually?

The  Ulam Spiral is the most famous.

 

[Emily Lake]

Aside from the cryptographic approach, primes are cool because they're not part of anything else. They're atoms. All the other numbers break down, like molecules being broken down into their constituent atoms. But primes don't break down. They're the building blocks.

In addition to that, if you lay out all of the integers in any pattern you want, then cross out all of the non-primes, the remaining primes almost, but not quite, make a pattern of their own. Since humans are nearly OCD when it comes to patterns, they fascinate us, trying to see the almost-pattern that isn't there, and trying to understand the formula-that-isn't that underlies them.

You have a link to any of these "almost-patterns" represented visually?

Prime Number Patterns

 

[Emily Lake]

My temporary descent into snarkiness aside...

View attachment Pictures%u002520of%u002520Prime%u002520Numbers.pdf

In addition to those already shown above by other posters.