MilestoneTheory & algorithmsConfirmed

Oded Regev proposes a new quantum algorithm for factoring

Aug 12, 2023

Oded Regev describes a quantum factoring algorithm that uses smaller circuits than Shor's, run independently about √n times for an n-bit number, with the results combined on a classical computer. Its correctness relies on an unproven number-theoretic assumption.

Why it matters

Factoring is what threatens RSA encryption. Regev's approach offers a different route from Shor's, though he notes it is not yet clear whether it can make real machines more efficient.

Oded Regev

See it on the timeline

Related

• Peter Shor shows a quantum computer could factor large numbers quickly (Nov 1994)
• Gidney and Ekerå estimate 20 million qubits could break RSA-2048 in eight hours (May 23, 2019)
• Google researcher estimates RSA-2048 could be broken with under a million qubits (May 2025)