在当今数字化时代，信息安全的重要性日益凸显，而公钥加密技术，尤其是Rivest-Shamir-Adleman（RSA）加密算法，作为保护数据传输和数字签名的基石，其安全性受到了广泛关注。RSA算法的安全性建立在大整数分解的计算难度之上，即如何将一个大的合数分解为两个质数的乘积。尽管随着计算技术的进步，这一问题在理论上仍被认为是困难的，但近期的研究进展表明，某些算法可能比预期的更接近于解决这一挑战。
10月21日，意大利帕多瓦大学、意大利国家核物理研究所、德国乌尔姆大学、意大利巴里大学在arXiv平台上发布题为“Quantum inspired factorization up to 100-bit RSA number in polynomial time”（多项式时间内高达100比特RSA数字的量子启发因数分解）的研究论文，Marco Tesoro为论文的第一作者。
在本文中，研究人员采用了一种称为张量网络方法的量子启发式算法。这种方法受到了量子计算的启发，但实际运行在经典计算机上。研究人员使用该方法，成功将100位的RSA数字分解问题编码到具有最多256量子比特的量子系统中，揭示了该算法在计算资源上的多项式时间复杂度。
这些成果得益于研究人员对Schnorr筛选算法的改进，通过引入张量网络（TN）技术来优化候选同余关系的搜索过程。结果表明，该方法在经典计算机上表现出了高效性，尽管其量子启发特性使其在某些方面与量子算法相似，但由于张量网络方法的限制，在量子计算机上可能不会像在经典计算机上那样高效。
此外，研究人员还提供了系统的数值分析，证明了所需资源随RSA密钥比特长度的多项式增长，这强烈暗示了利用该算法对RSA密钥进行因数分解可能仅需多项式计算资源。
背景
随着信息技术的飞速发展，公钥加密体系在现代通信安全中扮演着至关重要的角色。RSA加密协议作为经典的公钥加密标准之一，其安全性基于大数因数分解问题的计算复杂性。
传统上，因数分解大数被认为是一个指数级复杂度的任务，尤其是半素数，这使得RSA加密在实际应用中具有极高的安全性。然而，随着量子计算技术的不断进步，特别是Shor算法的提出，传统的RSA加密体系面临前所未有的挑战。Shor算法能够在多项式时间内分解大数，这对现有的加密体系构成了潜在威胁。
尽管目前量子计算机的发展仍处于初级阶段，尚不足以对实际应用中的RSA密钥构成实质性威胁，但这一潜在风险促使研究人员探索新的、能够抵御量子攻击的加密方法。在此背景下，寻找经典算法中可能存在的多项式时间因数分解方法成为一个重要的研究方向。这不仅有助于评估现有加密体系的安全性，还能为后量子密码学的发展提供重要参考。
本文提出了一种基于张量网络方法的经典算法，称为张量网络Schnorr格筛选算法（TNSS），用于解决RSA因数分解问题。该方法结合了Schnorr格筛选算法和张量网络技术。
Schnorr的格筛选算法将因数分解问题转化为一系列组合优化问题，即最近向量问题（CVP）。而张量网络技术则用于高效地表示和优化搜索过程中的量子态，从而有效地收集用于因数分解的平滑关系对（sr-pairs）。
具体来说，该算法通过构建与RSA数相关的CVP问题，并利用张量网络方法优化和采样这些CVP问题的解空间，最终找到用于因数分解的平滑关系对。
在实验中，研究团队利用张量网络Schnorr筛法成功地对高达100比特的RSA数进行了因数分解。他们首先构建了与RSA数相关的CVP问题，并通过张量网络方法对这些CVP问题进行了优化和采样。在采样过程中，他们采用了高效的OPES算法来避免重复采样相同的比特串，从而提高了采样效率。通过收集足够的平滑关系对，并利用线性代数方法进行处理，他们成功地找到了RSA数的两个质因数。
尽管TNSS算法的资源需求呈现出多项式增长，但这种高阶的多项式增长限制了其分解更大数字的能力。虽然这一成果尚未威胁到现有的通信安全，但它确实凸显了采纳后量子密码学或量子密钥分发技术的紧迫性。研究显示，TNSS算法可能只需多项式级别的经典资源就能分解RSA密钥。此外，尽管TNSS受到量子算法的启发，但由于其在张量网络中的实现和有限的量子关联，该算法能够在经典计算机上高效执行。
图5：展示了键维数与通过树张量网络从单个格中采样平滑关系对的关系
主要人员介绍
Marco Tesoro，意大利帕多瓦大学物理与天文学系博士生。
Ilaria Siloi，意大利帕多瓦大学物理与天文学系研究员。
参考链接
[1]https://arxiv.org/abs/2410.16355v1
[2]https://orcid.org/0009-0000-5194-3445
[3]https://orcid.org/0000-0002-3806-2034
