SoylentNews

Arthur T Knackerbracket has found the following story:

Math is hard. Indeed, much of the modern infrastructure for secure communication depends heavily on the difficulty of elementary mathematics — of factoring, to be exact. It's easy to reduce a small number like 15 to its prime factors (3 x 5), but factoring numbers with a few hundred digits is still exceedingly difficult. For this reason, the RSA cryptosystem, an encryption scheme that derives its security from the difficulty of integer factorization, remains a popular tool for secure communication.

Research suggests, however, that a quantum computer would be able to factor a large number far more quickly than the best available methods today. If researchers could build a quantum computer that could outperform classical supercomputers, the thinking goes, cryptographers could use a particular algorithm called Shor's algorithm to render the RSA cryptosystem unsalvageable. The deadline to avert this may arrive sooner than we think: Google recently claimed that its quantum computers will be able to perform a calculation that's beyond the reach of any classical computer by the end of the year. In light of this, cryptographers are scrambling to find a new quantum-proof security standard.

Yet perhaps RSA isn't in as much trouble as researchers have assumed. A few weeks ago, a paper surfaced on the Cryptology ePrint Archive that asked: "Is it actually true that quantum computers will kill RSA?" The authors note that even though a quantum computer running Shor's algorithm would be faster than a classical computer, the RSA algorithm is faster than both. And the larger the RSA "key" — the number that must be factored — the greater the speed difference.

-- submitted from IRC

Original Submission