4 ms·
Quantum computing is so powerful it takes two years to understand what happened
- tankenmate 12y agoTLDR; it appears that quantum computing can factor whole classes of numbers at once, not just single numbers. This may lead to even larger blacklists for RSA keys or even cripple RSA altogether.
- dalke 12y agoYour last sentence is conjecture, and not in the Register article or in the paper. (FWIW, jonbaer submitted a HN link to the paper last week.) The paper points that the reason why it works is because the factors are only off by two bits, eg. 3599 = 0b111011 * 0b111101 It also specifically addresses the RSA claim you made: > However, unless we know in advance that the factors will differ at two bits, this reduction will not allow us to crack big RSA codes.
- gus_massa 12y agoMore details in a friendly format: http://phys.org/news/2014-11-largest-factored-quantum-device.html http://phys.org/news/2014-11-largest-factored-quantum-device... From the research article: > In fact, it turns out that the product of any two numbers differing at only 2 bits will lead to the equations: > p_a + q_a = x (19) > p_b + q_b = y (20) > p_b q_a + p_a q_b = z, (21) > where the subscripts a and b correspond to the two bit-positions that differ, and the right-side variables {x, y, z} can each be 0 or 1 depending on the number being factored. However, unless we know in advance that the factors will differ at two bits, this reduction will not allow us to crack big RSA codes. This is interesting, but it's a very special family of numbers. When the numbers are more different they need more qbits.