中國研究人員提出新算法可利用量子計算機破解 RSA-2048，外國研究人員對此結果質疑。
2022 年 12 月，數學工程與先進計算國家重點實驗室、清華大學、浙江大學、北京量子信息科學研究院等國内知名機構研究人員在 arxiv 平台上傳了一篇題為 Factoring integers with sublinear resources on a superconducting quantum processor 的論文。論文指出，Shor 算法對基于公鑰的加密系統帶來挑戰。為破解廣泛使用的 RSA-2048 方案，需要數百萬量子比特，這超出了當前的技術能力。論文中提出一種通用的量子整數分解算法，該算法融合了經典的格規約 ( Lattice Reduction ) 和 QAOA（quantum approximate optimization algorithm，量子近似優化算法）。該方法所需的量子比特位 O ( logN/loglogN ) ，是截止目前最節省量子比特的分解算法。在實驗中，研究人員用 10 個超導量子比特可以分解 48 位整數。據估算，隻需要 372 個量子比特的計算機使用該算法就可以破解 RSA-2048 算法。
而 2022 年 11 月，IBM 就實現了 433 量子比特的量子計算機。因此，使用該算法加上 IBM 的量子計算機就可以破解 RSA-2048 算法。
随後，國外多名學者對該論文提出了質疑。美國密碼學專家布魯斯 · 施奈爾 （Bruce Schneier）認為論文提出的算法是依賴于 Peter Schnorr 論文中提出的算法，而該論文仍存在争議。此外，論文中隻在 10 量子比特的量子計算機上對 48 位數字就行了分解。這與 372 量子比特和 2048 位數存在很大差距。
論文下載地址：https://arxiv.org/pdf/2212.12372.pdf
https://www.scmagazine.com/brief/emerging-technology/chinese-researchers-report-breakthrough-in-quantum-computing
