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]

Cool! While you're at it, what are the factors of 18819881292060796383869723946165043980716356337941
73827007633564229888597152346654853190606065047430
45317388011303396716199692321205734031879550656996
221305168759307650257059?

[jhg.livejournal.com]

Actually, I did have a vague idea that Von Neumann computers couldn't do 'factors' - but surely saying 'The Factors Of 15 are 5 and 3' is surely an ill-thought out headline.

'Sides, Quantum Computer sounds exciting. Like Quantum Leap, or something.


J

[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