第三十七个知识点: The Number Field Sieve

数域筛法（The Number Field Sieve ,NFS）是已知的分解算法中最有效率的。它的运行时间取决于被分解的数的大小而不是它的因子的大小。NFS算法的分解基于平方同余理论：给定一个大整数\(N\)，我们想要找到两个不同的整数\(x\)和\(y\)使得\(x^2 = y^2 \mod N\)。然后我们希望\(gcd(x-y,N)\)是一个非平凡的A的因子。

我们大致描述一下NFS的工作原理。算法的第一步是选择两个yi'yuan不可约一元\(f_1\)和\(f_2\)分别有度\(d_1\)和\(d_2\)。让\(m \in Z\)是两个多项式共同的根\(f_1(m) = f_2(m) = 0 \mod N\)。让\(\theta_1,\theta_2 \in C\)是分别是\(f_1\)和\(f_2\)的复数根，我们构造两个代数域\(Z[\theta_i] = Q(\theta_i),i = 1,2\)。实际上这给出了两个乘法定义的多项式环。然后我们定义同态\(\phi_i : Z[\theta_i] \rightarrow Z_N\)，将\(\theta_i\)映射到\(m\)。NFS算法就是希望能从两个代数环中找出两个平方\(\gamma_1^2\)和\(\gamma_2^2\)，使得\(\gamma_1^2 = \Pi_{(a,b) \in S}(a-b*\theta_1)\)和\(\gamma_2^2 = \Pi_{(a,b) \in S}(a-b*\theta_2)\)，其中\(\gamma_1 \in Z[\theta_1],\gamma_2 \in Z[\theta_2]\)那么\(S\)是一个互素整数对的有限集合\((a,b)\)。为了找到这样的集合，我们将会对\(a-b*\theta_i\)进行筛选，通过观察\(a-b*\theta_i\)是否是在一些代数基数上平滑的进行筛选。我们多快发现集合\(S\)是算法效率的关键。接下来我们对\(\gamma_i^2\)进行开方，方法有[1]和[2]。一旦两个平方根被确定了，我们通过同态的性质\(\phi_1(\gamma_1)^2 = \phi_2(\gamma_2)^2 \mod N\)，同时期望\(gcd(N,\phi_1(\gamma_1)-\phi_2(\gamma_2)) \neq 1\)且\(gcd(N,\phi_1(\gamma_1)-\phi_2(\gamma_2)) \neq N\)是非平凡的因数。

[1] Couveignes, Jean-Marc. "Computing a square root for the number field sieve." The development of the number field sieve. Springer Berlin Heidelberg, 1993. 95-102.

[2] Montgomery, Peter L. "Square roots of products of algebraic numbers." Mathematics of Computation (1993): 567-571. APA