mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2003-06-17, 18:13   #1
sdbardwick
 
sdbardwick's Avatar
 
Aug 2002
North San Diego County

12528 Posts
Default "...[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.
sdbardwick is online now   Reply With Quote
Old 2003-06-17, 20:57   #2
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

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.
smh is offline   Reply With Quote
Old 2003-06-17, 20:58   #3
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·7·829 Posts
Default

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.
ewmayer is online now   Reply With Quote
Old 2003-06-17, 21:24   #4
ColdFury
 
ColdFury's Avatar
 
Aug 2002

1010000002 Posts
Default

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)
ColdFury is offline   Reply With Quote
Old 2003-06-18, 00:43   #5
jocelynl
 
Sep 2002

26210 Posts
Default

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
jocelynl is offline   Reply With Quote
Old 2003-06-18, 09:03   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

3·3,529 Posts
Default

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
xilman is offline   Reply With Quote
Old 2003-06-18, 14:16   #7
clowns789
 
clowns789's Avatar
 
Jun 2003
The Computer

17·23 Posts
Default

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?
clowns789 is offline   Reply With Quote
Old 2003-06-18, 14:42   #8
Complex33
 
Complex33's Avatar
 
Aug 2002
Texas

5·31 Posts
Default

I'd be willing to give for hardware or hosting for the new GIMPS server, if needed. Anyone else?
Complex33 is offline   Reply With Quote
Old 2003-06-18, 18:04   #9
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

22458 Posts
Default

Quote:
Originally Posted by clowns789
Also is GIMPS running if the computer is suspended?
No
smh is offline   Reply With Quote
Old 2009-10-27, 05:03   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×3,109 Posts
Default

...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.
Batalov is offline   Reply With Quote
Old 2009-10-27, 07:46   #11
sdbardwick
 
sdbardwick's Avatar
 
Aug 2002
North San Diego County

2×11×31 Posts
Default

I can't even remember what I found confusing at the time...
sdbardwick is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Higgs Boson and End of Universe? jinydu Lounge 5 2013-03-04 10:07
Can "Recent Result" list be longer? ATH PrimeNet 1 2011-07-08 14:48
Edge of the Universe. mfgoode Science & Technology 1 2007-01-01 01:04
Largest number in the real universe danjmi Science & Technology 17 2004-09-26 20:25
All the Universe on a stick HiddenWarrior Puzzles 24 2004-02-19 01:46

All times are UTC. The time now is 05:52.

Sat Feb 27 05:52:41 UTC 2021 up 86 days, 2:04, 0 users, load averages: 1.38, 1.38, 1.59

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

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.