How to understand and appreciate the prime number industry?

Why would I want to buy prime numbers? There is a website (found it!) selling a table of 400 digit primes for twenty dollars. Like an updated version of this. I have a layman’s idea that prime numbers are important to cryptography but surely for this low a price, I don’t think I can decrypt anything worthwhile. So what are the other uses that make prime numbers sellable at affordable home-user prices?

Hypothetically, if I accidentally discovered a huge prime, would its importance depend just on how big it is? What would make it “rare” enough that it’ll become my intellectual property to use commercially (number of hours a supercomputer takes to verify it? But what is the use?) This foundation gives prizes and for an amusing example, this guy claimed to have put his prime number for sale on ebay five years ago.

I also discovered that there were illegal primes forbidden for commercial distribution, but I am looking for some mathematical reasoning why they are illegal.

Any pointers to online or other resources which explain why there’s such a big deal behind the prime number industry would also be appreciated.

Answer

I would say that it’s almost a sham – not in the sense that it’s worthless, just that it markets to people who are apt to exaggerate its worth. Let’s consider a few of the things that people might do with such ‘bought’ primes: they might try to decrypt something, encipher something, or have some sort of sentimental value for a particular prime.

First: trying to decrypt something by buying lists of 400 digit primes. It seems to me that somehow, we have figured out that a message is enciphered using a 400 digit prime (likely the product of that prime and another, larger prime). We are trying to brute force attack it – but how many 400 digit primes are there? By the prime number theorem, we know there are about xlogx primes up to x, so we consider 10400400log1010399399log10, which is of the order 10398. Even if the list had each of these primes on it, just trying them all out is computationally improbable (to be… generous). It’s akin to saying: we know this door is locked by a key of about this size, so let’s get every such key in the world and try them.

Secondly: we are trying to encipher something. I will assume that we are going to use some public key cryptography and are trying to come up with something incoveniently large to decrypt, perhaps using RSA. But then we will probably use 2 primes, resulting in a number of over 800 digits. That’s annoyingly large. Worse, it is very easy to find your own 400 digit prime. One would expect to find one at random, by checking consecutive odd 400 digit numbers, every thousandth guess or so (1/400log10 numbers on average need to be checked, not counting the consideration of only even numbers). One would assume that needing such incredible security would mean that you at least own a computer, and therefore have the capabilities of finding your own large primes.

Thirdly, sentimental value. This reminds me of the ‘Name a Star after Someone’ campaign, like here. The author John Allen Paulos, I think, once quipped in his book Innumeracy that he should like to offer to name numbers after people, maybe charging more for prime numbers, etc.

But in regards to your fear of buying a number that someone else has bought – suppose that they choose 100 different 400 digit primes randomly for each list they sell. Then it wouldn’t be until something like their 10200th sale that we would expect someone to have bought the same number as you. However, if we consider this instead like the same-birthday ‘paradox,’ this number would be several dozen orders of magnitude reduced, and yet still meaninglessly large. There’s isn’t enough money in the world to get to that level.

In fact, they could name a different 400 digit prime after each human, every day, for longer than our sun will be around. I should start selling primes on ebay.

But the awards for computing larger and larger primes are not because of the use of the resulting prime number, but instead because it inspires development of computational and algorithmic methods. Finding large primes quickly becomes very, very challenging. I believe the current awards is for a prime of 100,000,000 digits, a very challenging number even to store in a computer’s memory, let alone manipulate.

Attribution
Source : Link , Question Author : kuch nahi , Answer Author : davidlowryduda

Leave a Comment