On Thu, 2 Oct 2003, Henry Baker wrote:
Does anyone know any more details about this announcement?
You mean, besides the fact that the author's understanding of even the basics of the factoring problem is appalling? I factored his "32-minute" number in about 30 seconds in my head! David Moulton
X-URL: http://story.news.yahoo.com/news?tmpl=story&u=/nf/20031002/bs_nf/22407
Researchers Create Super-Fast Quantum Computer Simulator Thu Oct 2, 3:03 PM ET
Mike Martin , sci.NewsFactor.com
...
Using conventional factoring algorithms, the time it takes to factor a number increases exponentially -- 2^N -- with the size of the number, where the exponent N is the number of digits. To factor the 5-digit number 65,448, for instance, it might take 2^5, or 32 minutes, using conventional computer algorithms.
In 1994, AT & T researcher Peter Shor created an algorithm based on quantum probabilities wherein the time required to factor a number grows only as a polynomial function -- N^2 -- of the number's size. N again is the number of digits.
In theory, factoring 65,448 with Shor's algorithm would take seven minutes less than with the conventional method -- 5^2, or 25 minutes.