"...[take] longer than the age of the known universe to

[sdbardwick]

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

[smh]

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

[ewmayer]

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.

[ColdFury]

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)

[jocelynl]

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

[xilman]

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

[clowns789]

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?

[Complex33]

I'd be willing to give for hardware or hosting for the new GIMPS server, if needed. Anyone else?

[smh]

Originally Posted by clowns789

Also is GIMPS running if the computer is suspended?

No

[Batalov]

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

[sdbardwick]

I can't even remember what I found confusing at the time...