点击查看原文

分享人：胡家祺 清华大学 博士研究生

内容简介

Shor算法揭示了通用量子计算机在整数因子分解问题上的高效性，极大的推动了量子计算领域的发展。然而，当前的量子计算机仍在含噪声中规模量子计算机（Noisy-Intermediate-Scale Quantum, NISQ）阶段，尚不能支持实用规模的Shor算法。近日，来自清华大学龙桂鲁教授团队的一篇论文基于密码学泰斗Schnorr的工作在超导量子计算机上分解了48位整数，对NISQ量子计算机破解RSA密码的潜力作乐观估计，引起了学界广泛的讨论和一定的争议。本次分享将结合整数因子分解领域的发展脉络，对该工作作较深入的解读，探讨NISQ量子计算机解决整数因子分解问题的潜力。

相关论文1

标题：Fast Factoring Integers by SVP Algorithms, corrected作者：Claus Peter Schnorr期刊：Cryptology ePrint Archive, Paper 2021/933

相关论文2

标题：Factoring integers with sublinear resources on a superconducting quantum processor作者：Bao Yan, Ziqi Tan, Shijie Wei, Haocong Jiang, Weilong Wang, Hong Wang, Lan Luo, Qianheng Duan, Yiting Liu, Wenhao Shi, Yangyang Fei, Xiangdong Meng, Yu Han, Zheng Shan, Jiachen Chen, Xuhao Zhu, Chuanyu Zhang, Feitong Jin, Hekang Li, Chao Song, Zhen Wang, Zhi Ma, H. Wang, Gui-Lu LongarXiv: 2212.12372 (2022)

相关论文3

标题：A comment on "Factoring integers with sublinear resources on a superconducting quantum processor"

作者：Tanuj Khattar, Noureldin Yosri

arXiv: 2307.09651 (2023)

相关论文4

标题：Pitfalls of the Sublinear QAOA-based Factorization Algorithm

作者：S.V. Grebnev, M.A. Gavreev, E.O. Kiktenko, A.P. Guglya, A.K. FedorovarXiv: 2303.04656 (2023)

量子计算的发展对密码学造成了深远的影响：1994年诞生的Shor算法证明通用量子计算机能够有效地解决整数因子分解问题，使得广泛应用的RSA加密体系不再安全并推动了抗量子密码技术发展。尽管Shor算法可能需要上百万个嘈杂的物理量子比特才能攻破RSA——当前的量子计算机只能提供上百个物理比特——已经有研究者尝试利用当前的中规模嘈杂量子设备（Noisy Intermediate Scale Quantum，NISQ）进行整数因子分解，甚至有研究者宣称只需要372个量子比特即可以攻破RSA-2048，掀起轩然大波。RSA是否已被或即将被量子计算机攻克？本文围绕该争议论文的来龙去脉为您解读。

核心内容：介绍整数因子分解问题的经典算法，光滑关系对，二次筛法和格方法的基础知识

整数因子分解是一个兼具学术和实用价值的问题。科学上，给定任意整数，尽管可以用Miller Rabin算法（该算法为多项式复杂度的随机算法）高效地判定其是否为素数，但求取其质因子则是高度困难的问题——尽管尚未被证明是否属于NP复杂性类。经典计算机上已知最高效的几个方法有：普通数域筛法（General Number Field Sieve，GNFS），二次筛法（Quadratic Sieve，QS），椭圆曲线因式分解（Elliptic Curve Method, ECM）等，如表1所示。知名的开源求解器有cado-nfs、msieve等。

附表1. 整数因子算法举例

以整数因子分解问题的困难性做安全性保障，RSA加密协议曾广泛应用数十年，其核心是对形如：

整数的分解问题，其中N为多达2048位的已知整数，而p, q均为待求的质数。RSA实验室甚至发布了RSA挑战赛榜单，鼓励用各种求解系统对大数作分解，促进了该领域发展的同时也体现了RSA加密体系在经典计算机上的安全性。然而，1994年IBM公司的Shor发现在通用量子计算机上可以在  

时间内分解N位整数，结合近年来量子计算领域的快速发展，对RSA加密体系产生了冲击，并推动密码学领域进入后量子时代。

目前的经典质因子分解算法，如GNFS、QS等通常基于光滑关系对（smooth relation pair）, 其原理是要构造平方同余关系对

从而得到N的因子

，如果Rabin-Miller算法判定其为合数，可以递归的分解。然而，平方同余关系对难以直接求得，实践中需要通过更容易求得的光滑关系对来构造。定义一个整数是B-光滑的，当且仅当其全体质因子都小于B。称两个整数x，y关于N构成B-光滑关系对，当且仅当x和y都是B-光滑的，且x≡y mod N. 现在假设已经采样到k个光滑关系对

，将每个光滑数分解为不超过B的质数

的乘积:

由此得到k组同余关系

现在要从k个光滑关系对中选出若干组，使得其乘积构成平方同余对。具体的，令

, 其第i个分量取1表示选中光滑关系对

。为了使得

和

均为完全平方数，t应当是同余方程组的解：

当光滑关系对的数目k≥2m时，可以保证同余方程组有解。同余方程组具体可以用Gauss消元法等方法在多项式时间内求解。

二次筛法不仅有较高的效率，原理也极为简洁。二次筛法利用了光滑数的分布规律：对于N≫1, 区间[1, N]内的B-光滑数ψ(N,B)有估计

其中ρ(u)是Dickman-de Bruijn函数，其在u→∞的行为近似是

。 由此可见，在更接近0的范围内采筛选得到光滑数的概率更高。由此构造二次函数

可见当 

时

， 通过筛法筛选出一组恰当的

，使得

为光滑数，而后通过解同余方程组再选出

, 使得

为平方数，由此得到

从而构造出平方同余对，有显著的几率获得质因子。

D. 格方法基础知识

格(lattice)在密码学中有广泛应用，篇幅所限，在此只介绍与论文相关的部分。由

中的基

可以定义格:

格问题中一般希望基向量尽可能的“正交”，Hadamard比率描述了格基的“正交”程度，定义为

即格基张成的平行多面体体积与对应的长方体的体积之比。通过对格基作整数系数的线性组合可以提高格的Hadamard比率，称作格约简(reduction)。LLL算法（K.Lenstra, H.W.Lenstra, Jr. and L.Lovasz）是经典的格约简算法.

格上的最短向量问题(Shortest Vector Problem, SVP)定义为

即寻找距离原点最近的格点。SVP已被证明是NP完备的。类似的，格上的最近向量问题（Closest Vector Problem, CVP）定义为

即要寻找距离给定的

最近的格点. CVP也是NP完备的。

如果将SVP和CVP中的目标松弛到最优解的γ>1倍，则相应的问题称作γ-SVP和γ-CVP问题，对足够大的γ有多项式算法。Babai的最近平面算法可以在多项式时间内求解

的γ-CVP问题，设

和

分别LLL约简基和Gram-Schmidt正交基（即对

正交化），Babai算法流程如下：

该算法有鲜明的几何意义：每一步迭代固定一个分量，即将候选的格点集合限制在分量对应的超平面中。那么，选取距离目标点t最近的超平面显然是合理的，这就是最近平面法。

图1. Babai算法的几何意义（来源：http://www.noahsd.com/mini_lattices/05__babai.pdf）

核心内容：Schnorr提出格方法求解整数因子分解，宣称攻破RSA加密体系（2021年）

这篇由著名密码学家Claus P. Schnorr（Schnorr签名的作者）在2021年发表的工作这项工作将光滑关系对的采样问题转化为格理论中的最近向量问题（Shortest Vector Problem, SVP），通过原对偶约简（prime-dual reduction）求解SVP，宣称攻破了RSA加密体系，曾引起广泛讨论和争议。现在一般认为并未攻破RSA，但其采用的方向确有重大的理论价值，参考同行Léo Ducas的公开复现结果SchnorrGate。

作者给出格的构造方案如下。设N是待分解的整数，

是前n个质数，

是整数集

上的置换，

，取格基为

设每个格点

编码了潜在的光滑关系对

记作

. 记

和

的最后一个分量分别为

则有

当且仅当

时取到等号. 借助Tayler展开式

可以证明：

引理：对于

，只要

或

，就有

由此

被

控制，后者可以通过求解SVP问题最小化。根据光滑数的分布规律，

构成光滑关系对的概率为

，其中ρ为Dickman-de Bruijn函数，

 . 通过设置不同的置换函数

并求解SVP问题，即可实现光滑关系对的采样。由此，光滑关系对采样问题转化为SVP求解。

 作者宣称求解n位整数因子分解问题只需要

维格，进而用

次算数运算可以分解

，比二次筛和数域筛更快。然而同行指出作者高估了采样成功率，也低估了所需的格的维数，各种公开和私下的复现结果最终导向共识：数域筛和二次筛仍然是最快的两个整数因子分解算法。

核心内容：清华大学龙桂鲁老师团队用基于QAOA改善Schnorr格方法的解，实现48bit整数分解，宣称372量子比特支持RSA-2048分解（2022年）

这篇文章沿用了Schnorr的工作，并用QAOA算法改进SVP解的质量（文中使用CVP形式，本质上和SVP相同），提出了亚线性资源的量子整数因子分解算法（Sublinear-resource Quantum Integer Factorization, SQIF），其整体框架如图所示。

图2. SQIF工作流程 （来源：arXiv:2212.12372）

作者用QAOA算法改进Babai算法的CVP解，其思想在约简格基下，对解（格点）的每个分量做±1的扰动（+1和-1只能选一个）或保持不动，以期得到更好的解。扰动的方向由Babai算法的取整的方向给出。具体的，设

和

分别是LLL约简基和相应的Gram-Schmidt正交基，Babai算法流程如下：

可见，Babai算法中计算系数c时对μ取整，当向下取整时，Babai算法给出的解的第j个分量比t大，应取-1作为扰动方向；当

是向下取整时，同理应取+1作为扰动方向。设

是Babai算法的解，扰动解构造为

其中

，符号选取如前所述。CVP问题表述为

这实质上是一个Ising问题，可以用QAOA算法求解，相应的哈密顿量为

其中

即将扰动映射到量子比特的Paoli-Z算符.

作者分别在11位数1961，26位数48567227和48位数261980999226229测试SQIF算法的效果，3用例分别使用了3个，5个和10个超导比特。如图2所示，超导量子计算机具有线性拓扑（A），而哈密顿量为全连接拓扑（B），故需要做比特映射。对于p层QAOA中的每一层演化（C），需要用

网络做路由（D），其

块可以由本地支持的Hadamard门和Rz门构建（E）。

图3.  SQIF算法的实验设置与QAOA量子线路 （来源：arXiv:2212.12372）

对不同的用例及QAOA层数p，作者给出的QAOA算法的仿真和实验结果如图所示。可见，QAOA算法的实际采样成功率与含噪声仿真（Noisy）结果接近，与无噪声仿真结果（Theory）相去甚远。对于3比特(p=3)，5比特(p=3)和10比特(p=1)情形，采样成功率分别在0.5， 0.2和0.01数量级。三种情况分别采样20，55和221个光滑关系对。据此可以估算所需的采样次数至少分别是

，

和

数量级。

图4. QAOA算法在三种因子分解用例上的实验表现. （来源: arXiv:2212.12372）

作者给出了考虑三种硬件拓扑下的线路深度估计。对三种有代表性的硬件拓扑：1）全连接拓扑Kn；2）1维链拓扑LNN；3）2维网格拓扑2DSL。对于n量子比特线路，每一层有n(n-1)/2个两比特ZZ耦合需要执行，三种情况下的作者给出的线路深度分别为

作者给出的线路实现分别是：

 Kn：全连接图划分为n组完美匹配，每组含n-1个ZZ单元，每个ZZ单元深度为3，共3n层；

LNN：将ZZ单元升级为兼具SWAP功能的ZZ-SWAP单元，每个ZZ-SWAP单元深度为4. 按照并行冒泡排序（parallel bubble sort）算法执行n层ZZ-SWAP完成演化，共计4n层。

2DSL：原理与LNN情形相同，但按照文献给出的方案优化到

层。

图5. ZZ单元（来源: arXiv:2212.12372） 

图6. 基于ZZ-SWAP单元的并行冒泡排序线路（来源: arXiv:2212.12372） 

综合以上结果，我们将作者演示的整数因子分解资源需求整理如下

附表2. SQIF算法资源估计

作者对分解不同规模RSA数所需的量子线路规模做乐观估计，认为用372个物理量子比特即可以攻破RSA-2048，由此引起广泛关注和争议。

附表3.  RSA整数因子分解在不同拓扑硬件上所需资源估计. 

Kn：全连接；2DSL：2维网格；LNN：1维链. 来源：来源: arXiv:2212.12372 Table 1

核心内容：Google团队对上述观点复现和评价，否定该方法直接可扩展性

这篇来自Google的论文回顾了Schnorr和Yan等人的争议性工作，并提供了一个公开的框架来测试像SQIF这样的格-QAOA量子经典混合算法的实际效果。其中，经典部分按照Schnor的工作，求解

维格上的CVP；量子部分则采用两种方法：其一是枚举经典解邻域的2m个格点，选取最优解；其二是模拟QAOA算法。显然，QAOA算法的效果不会优于枚举法。

测试使用的机器是Google Cloud Platform (GCP)上的一台 a2-highgpu-1g型虚拟机。该机器包含GPU，程序中的线性代数及可以向量化的运算被移动到GPU上以提供加速。

作者给出的测试结果如表所示。可见，枚举法未能分解任何70位以上的整数。作者由此断定：用基于格CVP解，QAOA等量子求解器无法将可求解问题的规模进一步增大。

附表4. SQIF算法的同行评测结果. （来源：https://arxiv.org/abs/2307.09651 ）

核心内容：俄罗斯团队对QAOA+格方法的评价，不赞成攻破RSA结论

这篇来自俄罗斯的论文指出了SQIF算法文章存在漏洞，即对算法的经典部分缺乏系统严谨的分析，并提供了若干用例来说明SQIF实际需要更多的资源来完成其所宣称的目标。具体的，作者指出了以下几个漏洞：

1.  无法保证QAOA算法能凑齐足够的光滑关系对。实验中，作者发现对N=1961，n=3，即使在构造格时用尽全部可能的置换，也只能凑齐9个光滑关系对，低于所需的数目；

2.  对算法复杂度分析不足，特别是“亚线性资源”的宣称是有误导性的：     (a) 一方面，经典部分使用的LLL算法只是γ-CVP算法，其中γ=(2/√3)^n，因此随问题规模增加，找到LLL算法给出短向量的概率指数下降；     (b) 另一方面，量子部分所用的QAOA算法在高维情形缺乏收敛性保证，而一些数值仿真表明这可能造成问题；

3. 超参数取值依据不清晰：例如，作者为了提高采样得到光滑关系对的概率，将用于验证的因子基大小

取为

，这会造成规模较大时求解线性同余方程组的代价快速增加；

4. 一些关于格的表述细节问题。

上述这些质疑可以为Google团队的对SQIF的复现结果一致，论证格方法+QAOA路线的可扩展性并没有人们想象的那样乐观。

本文介绍了一篇尝试在NISQ量子计算机上实现RSA大数分解的争议性文章，并介绍其来龙去脉。目前的结果显示，在当代的量子计算机上攻破RSA秘钥仍然是不太现实的。对于安全领域的从业者来说这似乎是一个好消息：在通用量子计算机诞生之前，我们仍有一些时间来开发抗量子密码，并升级生产系统中已有的协议。

欢迎专家学者在公众号投稿分享优秀论文和创新成果，投稿录取者可获得精美礼品一份，投稿联系HiQ量子计算小助手：LLT66TT（备注“量子计算专题投稿”） 

欢迎大家订阅“量子计算HiQ”，查看更多论文分享和学术活动信息