snopes.com  

Go Back   snopes.com > Urban Legends > Business

Reply
 
Thread Tools Display Modes
  #1  
Old 27 March 2014, 01:25 AM
mrwrite mrwrite is offline
 
Join Date: 12 February 2014
Location: Santa Cruz, CA
Posts: 14
Default 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.
Reply With Quote
  #2  
Old 27 March 2014, 01:45 AM
ganzfeld's Avatar
ganzfeld ganzfeld is offline
 
Join Date: 05 September 2005
Location: Kyoto, Japan
Posts: 22,875
Default

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...
Reply With Quote
  #3  
Old 04 April 2014, 08:12 AM
Skeptic's Avatar
Skeptic Skeptic is offline
 
Join Date: 16 July 2005
Location: Logan, Queensland, Australia
Posts: 1,735
Default

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.
Reply With Quote
  #4  
Old 04 April 2014, 08:19 AM
Richard W's Avatar
Richard W Richard W is offline
 
Join Date: 19 February 2000
Location: High Wycombe, UK
Posts: 25,075
Default

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
Reply With Quote
  #5  
Old 04 April 2014, 08:44 AM
ganzfeld's Avatar
ganzfeld ganzfeld is offline
 
Join Date: 05 September 2005
Location: Kyoto, Japan
Posts: 22,875
Icon605

True. Two years before that book was published, the EFF had already awarded 50 thousand USD for the first million digit prime number.
Reply With Quote
  #6  
Old 04 April 2014, 09:05 AM
Richard W's Avatar
Richard W Richard W is offline
 
Join Date: 19 February 2000
Location: High Wycombe, UK
Posts: 25,075
Default

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.
Reply With Quote
  #7  
Old 04 April 2014, 02:34 PM
GenYus234's Avatar
GenYus234 GenYus234 is offline
 
Join Date: 02 August 2005
Location: Mesa, AZ
Posts: 24,084
Default

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?
Reply With Quote
  #8  
Old 04 April 2014, 02:40 PM
Steve Steve is offline
 
Join Date: 19 October 2002
Location: Charleston, SC
Posts: 4,693
Default

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.
Reply With Quote
  #9  
Old 04 April 2014, 02:48 PM
GenYus234's Avatar
GenYus234 GenYus234 is offline
 
Join Date: 02 August 2005
Location: Mesa, AZ
Posts: 24,084
Default

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.
Reply With Quote
  #10  
Old 04 April 2014, 02:59 PM
Steve Steve is offline
 
Join Date: 19 October 2002
Location: Charleston, SC
Posts: 4,693
Default

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
Reply With Quote
  #11  
Old 04 April 2014, 08:11 PM
ganzfeld's Avatar
ganzfeld ganzfeld is offline
 
Join Date: 05 September 2005
Location: Kyoto, Japan
Posts: 22,875
Default

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
Reply With Quote
  #12  
Old 04 April 2014, 08:22 PM
Jay Temple's Avatar
Jay Temple Jay Temple is offline
 
Join Date: 25 September 2003
Location: St. Louis, MO
Posts: 9,104
Default

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?
Reply With Quote
  #13  
Old 04 April 2014, 08:28 PM
GenYus234's Avatar
GenYus234 GenYus234 is offline
 
Join Date: 02 August 2005
Location: Mesa, AZ
Posts: 24,084
Default

Probably not. Copyrights are for new creations, not discoveries. And I think Monsanto patents its seeds.
Reply With Quote
  #14  
Old 04 April 2014, 08:51 PM
Richard W's Avatar
Richard W Richard W is offline
 
Join Date: 19 February 2000
Location: High Wycombe, UK
Posts: 25,075
Default

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 257885161 - 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.
Reply With Quote
  #15  
Old 04 April 2014, 08:54 PM
Steve Steve is offline
 
Join Date: 19 October 2002
Location: Charleston, SC
Posts: 4,693
Default

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.
Reply With Quote
  #16  
Old 04 April 2014, 09:57 PM
Richard W's Avatar
Richard W Richard W is offline
 
Join Date: 19 February 2000
Location: High Wycombe, UK
Posts: 25,075
Default

Quote:
Originally Posted by Steve View Post
... 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.
Reply With Quote
  #17  
Old 04 April 2014, 10:19 PM
ganzfeld's Avatar
ganzfeld ganzfeld is offline
 
Join Date: 05 September 2005
Location: Kyoto, Japan
Posts: 22,875
Default

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.
Reply With Quote
  #18  
Old 04 April 2014, 10:31 PM
erwins's Avatar
erwins erwins is offline
 
Join Date: 04 April 2006
Location: Portland, OR
Posts: 11,275
Default

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.
Reply With Quote
  #19  
Old 08 April 2014, 12:04 AM
mrwrite mrwrite is offline
 
Join Date: 12 February 2014
Location: Santa Cruz, CA
Posts: 14
Default 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.
Reply With Quote
  #20  
Old 09 April 2014, 11:19 AM
Troberg Troberg is offline
 
 
Join Date: 04 November 2005
Location: Borlänge, Sweden
Posts: 11,580
Default

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.
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is On

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Former Israeli Prime Minister Sharon dead at 85 Psihala Soapbox Derby 2 11 January 2014 08:24 PM
UK Porn Ban: Prime Minister Declares War on Adult Content Mickey Blue Soapbox Derby 11 26 July 2013 03:54 PM
Australians Demand to Know Who Threw at Sandwich at Their Prime Minister BrianB Crash and Burn 11 10 May 2013 01:00 PM
Selling Mexican pot snopes Business 18 28 December 2010 12:45 PM
Welcoming the "Check" prime minister Mad Jay Politics 2 16 May 2007 12:07 AM


All times are GMT. The time now is 11:17 PM.


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