QUANTUM COMPUTER PERFORMS FIRST SUCCESSFUL FACTORING

[ciphergoth]

QUANTUM COMPUTER PERFORMS FIRST SUCCESSFUL FACTORING

IBM SCIENTISTS BUILD MACHINE THAT SOLVES MATHEMATICAL PROBLEMS WITH QUANTUM MECHANICS

NUMBER 15 FACTORED

FACTORS ARE 3 AND 5

http://www.research.ibm.com/resources/news/20011219_quantum.shtml

Comments

[ciphergoth.livejournal.com]

Various factoring algorithms exist. The simplest is "trial division" - try dividing by every odd number up to the square root until you find one that works. The fastest known for large numbers is called the General Number Field Sieve, and is frankly beyond my understanding at the moment. But we know of no way of factoring, say, 600-digit numbers even if we combined the entire computing resources of the world. If we could build a quantum computer with many thousands of qubits, that could do it.

There's a $10,000 prize for factoring the number I quoted, though, so I thouhgt it was worth a go...

http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html