6、整数分解的量子算法：从经典到量子的探索之旅

整数分解的量子算法：从经典到量子的探索之旅

1. 引言

整数分解问题（IFP）在密码学领域具有举足轻重的地位，著名的RSA加密系统的安全性就建立在IFP的难解性之上。RSA的发明者也因这一贡献在2002年获得了图灵奖，该奖项被誉为计算机科学领域的诺贝尔奖。如果IFP能在多项式时间内被解决，那么RSA以及众多其他加密系统将被高效破解。1994年，Shor提出了一种量子算法，能够在多项式时间内解决IFP，这为整数分解问题带来了新的突破。接下来，我们将深入探讨与量子分解相关的几个关键主题。

2. 经典整数分解算法

2.1 基本概念

整数分解有多种方法和算法。从算法的确定性角度来看，可分为确定性分解算法和概率性分解算法；若考虑待分解整数的形式和性质，则可分为通用分解算法和专用分解算法。
-通用分解算法：运行时间主要取决于待分解数n的大小，与找到的因子p的大小关系不大。常见的通用分解算法及它们的运行时间如下表所示：
| 算法名称 | 运行时间 |
| — | — |
| Lehman’s方法 | (O(n^{1/3 + \epsilon})) |
| Euler’s分解方法 | (O(n^{1/3 + \epsilon})) |
| Shanks’ SQUFOF方法 | (O(n^{1/4})) |
| Pollard和Strassen的基于FFT的分解方法 | (O(n^{1/4 + \epsilon})) |
| Coppersmith的基于格的分解方法 | (O(n^{1/4 + \epsilon})) |
| Shanks’