Selling prime numbers to the CIA
I read this odd question on a Q&A board.
"Does the CIA buy prime numbers?" Versions of this can be found on several Q&A sites. Typically the price is listed as $10,000 and the prime must be of 100 digits. (False, obviously. Fast computers can make as many as they need  for less.) I believe I may have found the start of this legend. In the book, "The Curious Incident of the Dog in the Night Time" Doubleday (US) 2003 There is this quote: "Prime numbers are useful for writing codes and in America they are classed as Military Material and if you nd one over 100 digits long you have to tell the CIA and they buy it o you for $10,000. But it would not be a very good way of making a living." If it wasn't the start of the rumor, it did help pass it along. The book was written in the UK and reprinted in the US. It won a few awards and recomendations. 
It is a work of fiction so it's not surprising that it contains fictions.
The Electronic Frontier Foundation does give awards for large primes. The next award is not 100 but 100,000,000 digits. The first was offered and awarded well before the book was published so maybe someone heard EFF and thought FBI (also often in the claim) and that became CIA... 
It must be noted that it's over ten years since the book was published and presumably the rumour started. Ten years is a long time both in terms of cryptography and in computing power.

Even ten years ago, 100 digits wasn't an unusually long prime. According to Wikipedia, primes of that length or more were known back in 1952. The current largestknown prime is 17,425,170 digits long!
http://en.wikipedia.org/wiki/Largest_known_prime_number 
True. Two years before that book was published, the EFF had already awarded 50 thousand USD for the first million digit prime number.

I hadn't heard the claim as a myth when I read the book, so it didn't jump out at me, but it does seem a likely origin if it's now something claimed as fact.
In the context of the book, the narrator's not supposed to be a reliable source of fact, so I guess it's Mark Haddon's deliberatelygarbled version of the EFF awards, distorted to reflect the main character's understanding. It's a good book, by the way. 
When buying a very large prime number, how can the buyer be sure that the number is prime? Wouldn't they have to run it through the very laborious process of elimination that was used to find it in the first place? If so, then wouldn't it be just as easy to find the number themselves?

I'm not sure, but I'd think that the initial person searching would have to run some algorithm on a large amount of numbers before finding one that's prime, whereas the person buying it would only have to recheck the prime number itself.

My understanding is that the algorithm to find primes works on all numbers, not one at a time. Simplified it goes like this:
Pick an upper limit of digits that will be the ceiling. Take the first prime number (2). Find all of its products up to the ceiling you've decided on. Take the first number not in the above set of products (3) which will also be prime. Find all of its products up to the ceiling. Do this with the first number not in any of the product lists (5, 7, 11, 13, 17, 19, 23, etc) in succession. When you hit a nonproduct number greater than the greatest known prime, you've got a new prime. I guess you could start analyzing a single prime number by reversing the process, but you'd still have to do all the calculations starting with a number that is 1/2 the prime. So I guess you could analyze 2 bought primes for the value of finding your own. 
That's the sieve of Eratosthenes, which works very slowly with larger numbers. There are other algorithms for numbers with 1000 digits, though I'm not really sure how they work. One example:http://primes.utm.edu/prove/prove4_1.html

In the case if the awards, it does take days (and multiple machines) to confirm any primes that are found but it's nothing compared to the problem of finding them in the first place. The specific primes they're finding are Mersenne Primes:
http://en.wikipedia.org/wiki/Great_I...e_Prime_Search 
Maybe this belongs in "Stupid Questions" ... Suppose, outside of any contest, someone finds a new prime number. Can they pull a Monsanto and copyright it, thereby requiring a royalty if, say, the CIA wants to use it for cryptography?

Probably not. Copyrights are for new creations, not discoveries. And I think Monsanto patents its seeds.

I'm going to have to go and look up some more maths, because (ahem) the details of how prime numbers are used as cryptographic keys has temporarily slipped my mind, but I may as well ask before I do so:
Does finding larger prime numbers even, in itself, help in cryptography, or if somebody said (for example) "Ha! Our algorithm uses a 17,425,170digit prime number and therefore is absolutely unbreakable!", would the other cryptographers just look at Wikipedia and say "I know what number that is  it's 2<sup>57885161</sup>  1" and be able to break the code? I'm fairly sure the answer is that the larger numbers do still help, but my reasoning is still too large to fit in this margin, so I'm going to wait until I've finished my tea to check it. (eta) I do know that there are probably many, many other 17,425,170digit primes than the one that's known, but it would be a reasonable assumption that the one meant would be the known Mersenne prime. 
The RSA algorithm for cryptography multiples 2 large primes together to get a larger composite and then [redacted] keeping your banking info safe. But yeah, you might be right that a "famous" prime (like the biggest currently known one) would therefore be useless since people could just try dividing the composite by the known prime.

Quote:
So yes, you need two large primes  and knowing one of those large primes would certainly help. Although probably not enough to let you work it out on your calculator. 
I haven't read the book in the OP but it sounds as if the author was trying to make a joke about the fact that large key encryption were once (until 1998?) classified as munitions that couldn't be exported. So it's like if you find a big prime number you have to report it to the government (in an extremely oversimplified and misunderstood version). Or maybe the character in the story (if not the author) was confused about the story (around the same time 1998) of the guy who was arrested for running primefinding software on a bunch of corporate computers without permission. Either way it was a time when the whole idea of primes being worth something and perhaps even dangerous in the wrong hands was in the news a lot.

It really is a very excellent book. Well worth reading.
The narrator is a boy most likely on the autism spectrum. He loves math, but doesn't always understand everything he hears people say. I don't know that Mark Haddon was trying to make a joke or a point other than showing the quirky sort of thing that the character would "know." Of course, it's possible that the book isn't the origin, in which case it's possible that Haddon included it thinking it was a fact, or if not, that it was the sort of thing Christopher would hear and believe. 
Brief answers
1. There are ways to prove a number is prime without factoring.
For example, Selfridge and Hurwitz showed that 14th Fermat number was composite in 1963, but no one knows any of the divisors to this day. (It is a really big number. They call it F14.) 2. Ecker primes, are found by first selecting random numbers of the size needed, and then checking to see if it is prime. (For 100digit primes the chance is about 8+ in 1000 are prime using the Ecker prime method. About .4% of 100digit numbers are prime. 3. Even if you know a 200 digit is made of two 100digit primes, it would still take a long time (and a bit of effort) to factor it. 4. Generally speaking, a number cannot be copyrighted. Neither can a list of numbers. 
Quote:

All times are GMT. The time now is 11:01 AM. 
Powered by vBulletin® Version 3.8.7
Copyright ©2000  2019, vBulletin Solutions, Inc.