Slashdot Mirror
New Quantum Computing Record Set By Recycled Photons
CelestialScience writes "A recycling technique has enabled a quantum computer to carry out a quantum calculation known as Shor's algorithm on a larger number than ever before. The benchmark algorithm exploits quantum mechanics to simplify the factorization of numbers into their prime components — a hard task for classical computers when the numbers get large. Until now, the largest number factorized using Shor's algorithm was 15. Now Anthony Laing at the University of Bristol, UK and colleagues report in Nature Photonics that they used a recycled photon to factorize 21 — still far too small and trivial to spook cryptographers, who rely on the difficulty of factorizing large numbers for their widely-used techniques. But a record nonetheless."
7*3. Nailed it!
Seen this before.
Are photons that expensive that they need to be recycled? I can understand aluminum cans, but photons are taking it a bit far, I think.
If I can be modded down for being a troll, can I be modded up for being an orc, or a balrog?
Even if it were more advanced now, it still wouldn't be much of a danger to cryptography.
There are enough encryption algorithms where quantum computing is not a danger.
Sure, algos using the dlog or factorisation problem would fall instantly, but something like McEliece would finally thrive.
15 is between 2^3 and 2^4. 21 is between 2^4 and 2^5. Next stop, 51!
the number 35 is standing out back with a tire iron and would like to have a word with you....
Note that quantum computers have already been used to factor larger numbers. As TFA discusses and this preprint http://arxiv.org/abs/1111.3726 from about a year ago reports, there has been success factoring 143. But they didn't use Shore's algorithm but rather used an adiabatic algorithm http://en.wikipedia.org/wiki/Adiabatic_quantum_computation. TFA makes a slightly incorrect claim that the adiabatic quantum algorithm "unlike Shore's algorithm, is not mathematically guaranteed to provide faster performance for larger numbers." This is misleading: Shore's is known to provide a polynomial time solution to factoring, but this is only known to be faster than the best known classical algorithms. In this context, we still can't prove that factoring is hard in the sense of taking more than polynomial time on a classical computer. Such a result is strictly stronger than P != NP http://en.wikipedia.org/wiki/P_versus_NP_problem which is one of the biggest unsolved problems of mathematics today.
Once, a long time ago, Slashdot was known as "news for nerds". We've come a long way, but every once in a while one of these sciency articles will slip through.
Simply pay this article no heed, good netzien, and I'm sure we can get back to our endless Apple vs Microsoft vs Linux vs liberal vs conservative vs cut vs uncut vs AMD vs Intel vs Oprah retard flame wars in no time. Wretched hives from the chans to even the AOL forums will be green with envy.
Nonsense. It is still unknown if it is possible (even theoretically) to scale this up. One of the main reasons is quantum decoherence which seems to introduce errors faster than you can scale the machine.
There are plenty of reasons to abandon RSA (which assumes factoring to be hard) in favor of elliptic curves but these quantum factoring advances are not one of them. RSA keys must be huge in order to provide similar security that symmetric and elliptic curve algorithms provide with small keys. Also, it's somewhat likely that the NSA has 1) improved GNFS or another factoring algorithm and 2) has built dedicated cracking hardware. I fully except the NSA to be able to factor 1024 bit numbers today (perhaps even at a rate of one or more a month).
This stuff scales incredibly bad with time. Not even a hint of a "Moore's law" here.
There is.
OS Reviews: Free and Open Source Software
Good thing RSA seems to be the only widely used crypto tool that will be broken by quantum computing. Symmetric ciphers and hash functions are thought to be resistant to quantum attacks (besides the necessary doubling of key sizes that applies to everything, due to Grover's algorithm). We also have assymetric ciphers based on lattice constructions that are quantum-resistant, ready to step in and take over if RSA ever becomes impractical.