snopes.com

snopes.com (http://message.snopes.com/index.php)
-   Business (http://message.snopes.com/forumdisplay.php?f=3)
-   -   Selling prime numbers to the CIA (http://message.snopes.com/showthread.php?t=89017)

mrwrite 27 March 2014 02:25 AM

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.

ganzfeld 27 March 2014 02:45 AM

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

Skeptic 04 April 2014 09:12 AM

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.

Richard W 04 April 2014 09:19 AM

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 largest-known prime is 17,425,170 digits long!

http://en.wikipedia.org/wiki/Largest_known_prime_number

ganzfeld 04 April 2014 09:44 AM

True. Two years before that book was published, the EFF had already awarded 50 thousand USD for the first million digit prime number.

Richard W 04 April 2014 10:05 AM

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 deliberately-garbled version of the EFF awards, distorted to reflect the main character's understanding.

It's a good book, by the way.

GenYus234 04 April 2014 03:34 PM

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?

Steve 04 April 2014 03:40 PM

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.

GenYus234 04 April 2014 03:48 PM

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 non-product 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.

Steve 04 April 2014 03:59 PM

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

ganzfeld 04 April 2014 09:11 PM

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

Jay Temple 04 April 2014 09:22 PM

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?

GenYus234 04 April 2014 09:28 PM

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

Richard W 04 April 2014 09:51 PM

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,170-digit 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,170-digit primes than the one that's known, but it would be a reasonable assumption that the one meant would be the known Mersenne prime.

Steve 04 April 2014 09:54 PM

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.

Richard W 04 April 2014 10:57 PM

Quote:

Originally Posted by Steve (Post 1813742)
... and then [redacted]

Aha, yes, the top secret "Appendix J" of Simon Singh's The Code Book. As he says, "Working this out directly on a calculator is not straightforward". And he's talking about the encryption!

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.

ganzfeld 04 April 2014 11:19 PM

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 prime-finding 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.

erwins 04 April 2014 11:31 PM

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.

mrwrite 08 April 2014 01:04 AM

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 100-digit primes the chance is about 8+ in 1000 are prime using the Ecker prime method. About .4% of 100-digit numbers are prime.
3. Even if you know a 200 digit is made of two 100-digit 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.

Troberg 09 April 2014 12:19 PM

Quote:

4. Generally speaking, a number cannot be copyrighted. Neither can a list of numbers.
Interesting, as any digital data (such as a DVD movie, an MP3 file or a program) is exactly that, just a list of numbers, or, if you prefer to read it that way, a very long number.


All times are GMT. The time now is 01:46 PM.

Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2019, vBulletin Solutions, Inc.