20030617, 18:13  #1 
Aug 2002
North San Diego County
2×11×31 Posts 
"...[take] longer than the age of the known universe to
... find the factors of a number with 300 digits."
Michael Hiltzik, "Harnessing Quantum Bits", MIT Technology Review, March 2003, page 61. Full sentence reads: "To factor the number 6 is trivial, but experts estimate it would take all the supercomputers in the world longer than the age of the known universe to find the factors of a number with 300 digits." I was browsing the print magazine and thought this was a rather strange statement. Then again, I cannot rule out my having a fundamental misunderstanding of what is considered a factor... I hope somebody with a deeper understanding can comment. 
20030617, 20:57  #2  
"Sander"
Oct 2002
52.345322,5.52471
29×41 Posts 
Quote:
But i guess the article was talking about 2 factors of about the same size (150 digits). The current records for numbers of a special form are the factorizations of 227 digit composites of 2^7511 and 2^773+1 (but i guess the current nfsnet.org group should be able to beat this record within a year). The record for a general number is the factorization of RSA 160, so this is still a long way off. 

20030617, 20:58  #3 
∂^{2}ω=0
Sep 2002
República de California
3×5^{3}×31 Posts 
The statement is undoubtedly referring to the most difficult such instance, the one where the number in question is composite (this is easy to check, without even being able to find any factors) and has no small (< 60 digits or so) factors that could be found in any reasonable amount of time using existing computer hardware and algorithms. The cost of factoring such numbers goes up exponentially fast, so it is probably an accurate statement.
Of course as few as 30 years ago the same statement could have been applied to numbers of just 100 digits (and improved algorithms have had at least as much to do with this progress as faster computers), so such pronouncements tend to become obsolete fast. It's a typical pronouncement by the quantum computing crowd, because as they well know, factoring is one of the computational tasks which can be done exponentially faster via QC than via classical computation  300digit numbers will be trivial for QCs to factor. Interestingly, if I recall correctly it has recently been proven (alas, I forgot to save the link, but I believe it was a paper in either Nature or Science) that there are in fact only TWO fundamental types of algorithms which can be speeded up exponentially by QC: factoring and database search. That means that there is a huge variety of problems whose solution will not be trivial even with QC  advocates of the latter tend to sweep that lil' skeleton under the rug. 
20030617, 21:24  #4  
Aug 2002
2^{6}·5 Posts 
Quote:
And even though Grover's algorithm can't speed things up exponentially, it can be generalized far beyond database searching. Things like breaking symmetric ciphers and finding hash collisions can be done with Grover's algorithm. (Anything that can be described with an oracle function can be adapted to Grover's algorithm) 

20030618, 00:43  #5 
Sep 2002
2·131 Posts 
Put all the computers in the world at work on this 300 digits numbers and you might get 4 billons years of work in no time.
Joss 
20030618, 09:03  #6  
Bamboozled!
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across
2·5,323 Posts 
Quote:
NFSNET should indeed be able to break the record reasonably soon if we get more clients helping out (hint!). Paul 

20030618, 14:16  #7 
Jun 2003
The Computer
110001000_{2} Posts 
Maybe we could use PayPal to get GIMPS more money and possibly the biggest supercomputer in the world. Also is GIMPS running if the computer is suspended?

20030618, 14:42  #8 
Aug 2002
Texas
5·31 Posts 
I'd be willing to give for hardware or hosting for the new GIMPS server, if needed. Anyone else?

20030618, 18:04  #9  
"Sander"
Oct 2002
52.345322,5.52471
29·41 Posts 
Quote:


20091027, 05:03  #10 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
41·229 Posts 
...and six years later, it is clear why this statement is in the "Fun Stuff" category.
Where is Michael Hiltzik now? LA Times? Wow... Fun Stuff. 
20091027, 07:46  #11 
Aug 2002
North San Diego County
2·11·31 Posts 
I can't even remember what I found confusing at the time...

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Higgs Boson and End of Universe?  jinydu  Lounge  5  20130304 10:07 
Can "Recent Result" list be longer?  ATH  PrimeNet  1  20110708 14:48 
Edge of the Universe.  mfgoode  Science & Technology  1  20070101 01:04 
Largest number in the real universe  danjmi  Science & Technology  17  20040926 20:25 
All the Universe on a stick  HiddenWarrior  Puzzles  24  20040219 01:46 