Korva is a scroll of the internet’s best ideas.
Quantum computers barely factor 15
Current machines are very noisy, so they need lots of duplicate qubits for noise reduction and error correction. Everything depends on controlling the phase of the waves very precisely. When a system couples to its environment, lots of tiny phase differences wash out the quantumness, which is why so many quantum computing systems go to heroic lengths to cut off the environment, with ultra high vacuum and low temperature.
Even factoring 15 is a massive effort on a quantum computer, and a 2,000-bit RSA problem is far beyond it. Nobody knows when a quantum computer will be big enough to do it. It could be in 5 years, more realistically 20 or 30, or it could be hundreds of years. Such a machine would affect all of our cryptographic algorithms.
Why does noise ruin quantum calculations?
A qubit that interacts with its surroundings becomes entangled with them, and the phase information the calculation depends on leaks away. This process is called decoherence. Quantum error correction fights it by spreading one logical qubit across many physical qubits and checking for errors without reading the data directly. Peter Shor devised the first quantum error-correcting code in 1995, using nine qubits.
Why was 15 the first number factored?
The number 15 is the smallest odd number that is the product of two different primes, 3 and 5. In 2001, an IBM team led by Lieven Vandersypen ran Shor's algorithm on a seven-qubit nuclear magnetic resonance machine and factored 15. The result was published in the journal Nature. Larger demonstrations since then have needed far more careful tricks than the general algorithm.
How are cryptographers preparing for quantum computers?
In August 2024, the US National Institute of Standards and Technology published its first three post-quantum encryption standards: FIPS 203, FIPS 204, and FIPS 205. Two of them rest on lattice problems, which have no known efficient quantum attack. The third is a signature scheme built only from hash functions. NIST began the selection process in 2016 with a public call for submissions.