mersenneforum.org "...[take] longer than the age of the known universe to
 Register FAQ Search Today's Posts Mark Forums Read

 2003-06-17, 18:13 #1 sdbardwick     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.
2003-06-17, 20:57   #2
smh

"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts

Quote:
 ......longer than the age of the known universe to find the factors of a number with 300 digits."
It'll all depend on the size of the factors. Factors smaller then 35 digits are easy to find. Factors of 45 to 50 digits are harder to find but very well possible with enough effort.

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^751-1 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.

 2003-06-17, 20:58 #3 ewmayer ∂2ω=0     Sep 2002 República de California 3×53×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 - 300-digit 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.
2003-06-17, 21:24   #4
ColdFury

Aug 2002

26·5 Posts

Quote:
 speeded up exponentially by QC: factoring and database search.
Actually, Grover's algorithm doesn't speed up database searching exponentially, only by a factor of a square root roughly. QCs can do discrete logs (and elliptic discrete logs too) with exponential speed up. This isn't surprising because they both can be transformed into a hidden subgroup problem, which Shor's algorithm can be generalized to solve.

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)

 2003-06-18, 00:43 #5 jocelynl   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
2003-06-18, 09:03   #6
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2·5,323 Posts

Quote:
 Originally Posted by smh The current records for numbers of a special form are the factorizations of 227 digit composites of 2^751-1 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.
As far as I know, the current record for SNFS is 2^809-1 which was done by Jens Franke et al a few months ago. Again AFAIK, RSA-160 is the largest GNFS yet done.

NFSNET should indeed be able to break the record reasonably soon if we get more clients helping out (hint!).

Paul

 2003-06-18, 14:16 #7 clowns789     Jun 2003 The Computer 1100010002 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?
 2003-06-18, 14:42 #8 Complex33     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?
2003-06-18, 18:04   #9
smh

"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts

Quote:
 Originally Posted by clowns789 Also is GIMPS running if the computer is suspended?
No

 2009-10-27, 05:03 #10 Batalov     "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.
 2009-10-27, 07:46 #11 sdbardwick     Aug 2002 North San Diego County 2·11·31 Posts I can't even remember what I found confusing at the time...

 Similar Threads Thread Thread Starter Forum Replies Last Post jinydu Lounge 5 2013-03-04 10:07 ATH PrimeNet 1 2011-07-08 14:48 mfgoode Science & Technology 1 2007-01-01 01:04 danjmi Science & Technology 17 2004-09-26 20:25 HiddenWarrior Puzzles 24 2004-02-19 01:46

All times are UTC. The time now is 02:32.

Sat Apr 17 02:32:32 UTC 2021 up 8 days, 21:13, 0 users, load averages: 2.37, 2.20, 2.10

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.