ResearchPod Summary
This paper presents a comprehensive formalization of Shor's algorithm and its variants within the Lean theorem prover. By utilizing an agentic formalization workflow—where software agents assist in proof construction and repair while humans review scientific claims—the authors verify the mathematical foundations and resource requirements for attacking RSA-2048 and the P-256 elliptic curve. The study bridges the gap between abstract quantum algorithm descriptions and concrete, machine-checked resource estimates.
The authors employ a modular approach to formalization, developing reusable mathematical layers for number theory, probability, and reversible arithmetic. The workflow relies on Lean's ability to handle executable definitions and formal proofs, integrated with agentic systems that search and extend existing libraries. For RSA-2048, the formalization covers the order-finding reduction, reversible modular arithmetic, and the Ekerå–Håstad recovery procedure. For P-256, it covers discrete logarithms in finite cyclic groups, prime-field arithmetic, and elliptic-curve point operations. Each step is verified by the Lean kernel, ensuring that the final claims regarding success probabilities and resource counts are logically sound.
The study produces two primary theorems that provide quantitative guarantees for quantum attacks. For RSA-2048, the authors demonstrate a quantum algorithm that returns a prime factor with a success probability of at least 2/3, utilizing 6,190 logical qubits and 8.1 billion Toffoli gates. For P-256, the formalization confirms a scalar-recovery algorithm with a success probability of at least 2/3, requiring 2,330 logical qubits and 126 billion Toffoli gates. These results represent a significant advancement in machine-checked quantum cryptanalysis, providing a rigorous foundation for evaluating the security of cryptographic standards against future quantum threats.
As quantum computing matures, the ability to formally verify the correctness and resource costs of quantum algorithms becomes critical for cryptographic security. This work demonstrates that complex, multi-stage quantum algorithms can be fully formalized and verified, reducing the risk of errors in manual analysis. By providing a reusable library of verified quantum components, the authors pave the way for more efficient and reliable AI-assisted design and verification of future quantum algorithms.
AI-generated third-party summary by ResearchPod. Not official content or an endorsement by the paper authors or affiliated organizations.