# 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.

-
As far as I know, the illegality of illegal primes has nothing to do with their primality and everything to do with what their bits can be interpreted to be. – Qiaochu Yuan May 24 '11 at 8:24
@Sebastien: I would not trust a prime I bought. It could be, that the vendor also sold it to someone else. – FUZxxl May 24 '11 at 8:54
What prime number industry? – lhf May 24 '11 at 12:05
Lowest prime whose factors are not obvious? I thought that the factors of any prime $p$ are obvious, namely $1$ and $p$. ;-) – Luboš Motl May 24 '11 at 13:42
+1 for making me learn what an illegal prime is! – Eric Naslund May 24 '11 at 14:21

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 $\frac{x}{\log x}$ primes up to x, so we consider $\dfrac{10^{400}}{400 \log 10} - \dfrac{10^{399}}{399 \log 10}$, which is of the order $10^{398}$. 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/{400 \log 10}$ 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 $10^{200}$th 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.

-
As FUZxxl comments, I wouldn't worry about somebody else having discovered the prime if I wanted to use it for encryption, but I would worry about the people who sold it to me keeping a record and using it. – Ross Millikan May 24 '11 at 17:41

What you get for your \$20 is a fixed list of half a billion primes of various sizes. If that's what you want, the price looks very reasonable -- it would take me months to generate a comparable list on my laptop. The only problem is that they don't say how they selected which primes to include in the list -- are they the first$n$primes in the given range, or are they uniformly selected, or what? This makes them less reliable as input to a test suite, which is the most likely use for them. - This website is probably a student project or a personal project of a programmer. Trying out things like paypal etc. - Don't make it bigger than it is. - It might be the case that there are some researchers trying to find some patterns in prime numbers :) so buying this at 20$ would make complete sense even if we are sold incomplete lists.

-