What is the significance of prime numbers in cryptography?

[_Mayday_]

Hey Everyone,

People keep on telling me that the biggest prime number known to man, is used for things like credit cards, how, I do not know, but I am hearing it more and more and need to know, because people think they are clever when they say it, but they have no further knowledge about it! Another question, what is that prime number? I have also heard that if you find the one after that one you get a hell of a lot of money. How would you go about finding it, because I want a lot of money.

Please don't move this maths forums, this isn't about the maths, but about the story around the maths.

_Mayday_

 

[rewebster]

http://www.math.utah.edu/~pa/math/largeprime.html

m39 = 213,466,917-1

"In the decimal system it requires 4,053,946 digits to be written fully"

update:

http://primes.utm.edu/largest.html#largest

 

[Borek]

So far you don't use THAT huge primes for credit card security, I think around 512 bits is still enough (albeit you need two of them ).

 

[dst]

I have also heard that if you find the one after that one you get a hell of a lot of money. How would you go about finding it, because I want a lot of money.

With a supercomputer and a sieve. Everyone has those lying around.

 

[BryanP]

Super-computers are generally used to try to find these primes. There's tons of people out there even contributing to find these primes.

It's not easy to get unless you've found some miraculous algorithm to solve for a large number prime (up to at least what we have now) in record time. But that task itself isn't even easy.

 

[humanino]

I have also heard that if you find the one after that one you get a hell of a lot of money. How would you go about finding it, because I want a lot of money.

The money assigned to finding large prime numbers is not for the primes themselves, but for novel ways to investigate them. It is not just a matter of time to accomplish this, it is also a matter of cleverness/genius.

By the same token, people try to calculate more digits of pi, although we already have much much much more than what is necessary for practical purposes. Once again, it is a matter of algorithms.

The reason prime numbers are used to send secret (or secured) messages is that factorization is difficult. A prime number cannot be divided in the product of two other integers. Take two very large prime numbers (say 150 digits as indicated above) and multiply them together. Then give us the result of your multiplication. You can bet whatever you want that nobody will be able to find the prime numbers you started from within the next few weeks or even months, unless they huge massive supercalculators.

Consider the big product of two prime numbers as a padlock, easily unlocked if you know any of the two primes it is made of. Now somehow, you could send this padlock "open" to your friend, he locks his box with it and send it all back to you. You can unlock it. Nobody has been able to open the box containing the secret (or secured) data. And you can use your credit card on internet

edit
the details of how you lock/unlock or encrypt/decipher your data is mostly technical.