factorization

3 Articles

Why Haven’t Quantum Computers Factored 21 Yet?

February 9, 2026 by 28 Comments

If you are to believe the glossy marketing campaigns about ‘quantum computing’, then we are on the cusp of a computing revolution, yet back in the real world things look a lot less dire. At least if you’re worried about quantum computers (QCs) breaking every single conventional encryption algorithm in use today, because at this point they cannot even factor 21 yet without cheating.

In the article by [Craig Gidney] the basic problem is explained, which comes down to simple exponentials. Specifically the number of quantum gates required to perform factoring increases exponentially, allowing QCs to factor 15 in 2001 with a total of 21 two-qubit entangling gates. Extrapolating from the used circuit, factoring 21 would require 2,405 gates, or 115 times more.

Explained in the article is that this is due to how Shor’s algorithm works, along with the overhead of quantum error correction. Obviously this puts a bit of a damper on the concept of an imminent post-quantum cryptography world, with a recent paper by [Dennish Willsch] et al. laying out the issues that both analog QCs (e.g. D-Wave) and digital QCs will have to solve before they can effectively perform factorization. Issues such as a digital QC needing several millions of physical qubits to factor 2048-bit RSA integers.

Bad RSA Library Leaves Millions Of Keys Vulnerable

October 17, 2017 by 20 Comments

So, erm… good news everyone! A vulnerability has been found in a software library responsible for generating RSA key pairs used in hardware chips manufactured by Infineon Technologies AG. The vulnerability, dubbed ROCA, allows for an attacker, via a Coppersmith’s attack, to compute the private key starting with nothing more than the public key, which pretty much defeats the purpose of asymmetric encryption altogether.

Affected hardware includes cryptographic smart cards, security tokens, and other secure hardware chips produced by Infineon Technologies AG. The library with the vulnerability is also integrated in authentication, signature, and encryption tokens of other vendors and chips used for Trusted Boot of operating systems. Major vendors including Microsoft, Google, HP, Lenovo, and Fujitsu already released software updates and guidelines for mitigation.

The researchers found and analysed vulnerable keys in various domains including electronic citizen documents (750,000 Estonian identity cards), authentication tokens, trusted boot devices, software package signing, TLS/HTTPS keys and PGP. The currently confirmed number of vulnerable keys found is about 760,000 but could be up to two to three orders of magnitude higher.

Devices dating back to at least 2012 are affected, despite being NIST FIPS 140-2 and CC EAL 5+ certified.. The vulnerable chips were not necessarily sold directly by Infineon Technologies AG, as the chips can be embedded inside devices of other manufacturers.

Continue reading “Bad RSA Library Leaves Millions Of Keys Vulnerable” →

Shor’s Algorithm In Five Atoms

May 1, 2016 by 26 Comments

If you want to factor a number, one way to do it is Shor’s algorithm. That’s a quantum algorithm and finds prime factors of integers. That’s interesting because prime factorization is a big deal of creating or breaking most modern encryption techniques.

Back in 2001, a group at IBM factored 15 (the smallest number that the algorithm can factor) using a 7 qubit system that uses nuclear magnetic resonance. Later, other groups duplicated the feat using photonic qubits. Typical implementations take 12 qubits. However, recent work at MIT and the University of Innsbruck can do the same trick with 5 atoms caught in an ion trap. The researchers believe their implementation will easily scale to larger numbers.

Each qubit is an atom and LASER pulses perform the logic operations. By removing an electron to make each atom positively charged, an electric field can exactly hold the positively charged ions in position only microns apart.

We’ve covered quantum computing before. We’ve even talked about the effect of practical quantum computing on encryption. You might also want to read more about the algorithm involved.

Photo credit: Jose-Luis Olivares/MIT