选定 RSA 数的因子分解算法

• 下载源代码 - 1.17 KB

引言

RSA要求我们选择两个随机的素数p和q，并用它们生成一个数字n = p*q。n被称为半素数，因为它只有两个因子（除了数字1）。为了通过研究不同的方法来了解因式分解，一种方法是尝试推断p+q这个重要值。因子p和q的和可以用来分解n=p*q。

背景

实现的方法之一使用以下多项式来表示分解半素数n的问题

x^2 - (p+q)x + pq = 0

这允许我们使用二次方程[2]，通过将系数设置为a = 1，b = -(p+q)，c = pq，在一般方程中推导出因子p和q

ax^2 + bx +c = 0

因此，代入二次公式[2]

x = (-b +- sqrt(b^2 – 4ac))/2

我们得到以下解决方案

p+q +- sqrt( (p+q)^2 - 4 * pq )               (Equation 1)
--------------------------
                    2

作为一个简单的例子，考虑n=3*7=21。我们现在有

x^2 - (3+7)x + 21

根据我们对二次方程的使用，得到公式

10 +- sqrt ((10^2) - 4 * 21)
----------------------------
            2

求解以下情况

10 + sqrt ((10^2) - 4 * 21)
---------------------------- = 7
            2

而，对于以下情况

10 - sqrt ((10^2) - 4 * 21)
---------------------------- = 3
           2

这允许我们重现因子3和7。这意味着如果我们能以某种方式推断出和p+q，我们就可以轻易地分解n。

我们注意到我们有

(p + q)^2 – (p – q)^2 = 4 * pq  (Equation 2)

我们可以通过平方p+q和p-q并求解来证明这个陈述

          p^2 + 2 * pq + q^2 – [p^2 – 2 *pq + q^2] = 4 * pq
          p^2 + 2 * pq + q^2 – p^2 + 2 *pq – q^2 = 4 * pq
                      2 * pq + 2 * pq = 4 * pq
                              4 * pq = 4 * pq

鉴于此，我们可以将半素数分解的问题重述为勾股定理的应用

c^2 = a^2 + b^2

其中c = p + q，a = p – q，b = sqrt(4 * pq)，因此

(p + q)^2 = (p – q)^2 + (sqrt(4 * pq))^2

这是因为

(p + q)^2 = (p – q)^2 + 4 * pq    (square the square root yields 4 * pq)
(p + q)^2 – (p – q)^2 = 4 * pq    (subtracting (p-2)^2 from both sides)

这是方程2。使用这个，我们可以写出p+q是

p + q = sqrt((p – q)^2 + 4 * pq)         (Equation 3)

这源于勾股定理。

给定方程3并注意到右手边必须是一个完全平方数，以便我们能够产生整数因子n，我们可以设计一个O((p – q)/2)的分解算法。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int
main(int argc, char **argv)
{
    if(argc != 2) {
         fprintf(stderr, “syntax: factor semi_prime\n”);
         return 1;
    }
    {
         int n = strtoul(argv[1], NULL, 10);
         int i  = 2, j = 0, k = 0, trials = 0, p = 0, q = 0;
         if((n % i) == 0) {
             /* Divisible by 2. */
             printf(“n=%d p=%d q=%d trials=1\n”, n, i, p/i);
             return 0;
         }
         for(; i < n; i += 2, ++trials) {
              j = ( i * i );
              j = j + 4 * n;
              k = (int)sqrt(j);
              if((k * k) == j) {
                  /* k == p + q, i == p – q */
                              p = (k + i) / 2; 
                  q = (k – i) / 2;
                  printf(“n=%d p=%d q=%d trials=%d\n”,n,p,q,trials);
                  return 0;
              }
         }
    }
    return 0;
}

应该清楚，该算法的复杂度为O((p – q)/2)。算法在找到完全平方数时停止，该完全平方数由以下if语句为真时确定

if ((k * k) == j)

而这正好发生在i等于p-q时。由于我们从i==2开始计数，每步加2，我们只需要一半的步骤就能找到一个因子。其中一个因子（p或q）为2的情况被视为特殊情况。此外，p和q相同（因此n是完全平方数）的情况不被该算法处理。该算法允许我们以多项式时间分解因子之间存在可数差的半素数。对于p和q差异很大的情况（就像真实世界的RSA引擎一样，我们希望如此），该算法是不可行的。

欧拉Phi的应用

现在我们转向欧拉Phi[1]函数。在这里，我们从欧拉Phi函数关于半素数n=p*q（其中p和q是不同的素数）的定义中计算了一些结果。推导出了以下结果

令eulerphi(n)等于(p-1)*(q-1)，对于半素数。然后我们通过展开(p-1)*(q-1)计算eulerphi(n)为p*q - p - q + 1。

因此，n = eulerphi(n) + p + q - 1。如果我们令x = p + q，我们可以说n = eulerphi(n) + x - 1。解出x，得到

x = n - eulerphi(n) + 1，因此

p+q = n - eulerphi(n) + 1。

现在，给定多项式：x^2 - (p + q)x + pq，我们可以使用二次公式来推导出n的因子p和q，如前所述。只是这次计算了欧拉Phi的值。因此，如果我们能计算出n的欧拉Phi，我们就可以轻松地分解n。

为了实现这个想法，我们使用了pari/GP，可以从http://www.ufr-mi.u-bordeaux.fr/~belabas/pari获得，并使用GP编写以下脚本

n=312825222036352242636619;
phi=eulerphi(n);
p_plus_q=n-phi+1;
sq=p_plus_q*p_plus_q;
t=sq-4*n;
determinant=sqrt(t);
p=(p_plus_q+determinant)/2;
q=(p_plus_q-determinant)/2;
 
print ("factoring: " n);
print ("q: " q);
print ("p: " p);
\q

文章中包含一个名为gen_prime.java的程序，该程序使用所需的位数作为指导来生成随机素数。此工具将用于测试我们的基于欧拉Phi的因式分解。例如，Linux命令行

echo "`java gen_prime 64` * `java gen_prime 64`" | bc

将生成一个128位半素数。

现在，考虑到我们用于推导随机素数的Java代码，另一个脚本用于测试使用这些生成的随机素数的几个案例。

这些值相乘后，将作为GP因式分解脚本中的n值。

然后，我们让pari求解方程并产生结果。欧拉Phi应用的一个例子

parisize = 4000000, primelimit = 500000
factoring: 312825222036352242636619
q: 63060978419.00000000000000000
p: 4960678217801.000000000000000
Goodbye!

相比之下，Linux上当前的“factor”命令产生以下结果

$ factor 312825222036352242636619
factor: `312825222036352242636619' is too large

运行的测试脚本可在test_eulerphi.sh中找到。它允许用户自定义脚本，通过将脚本变量PRIMES设置为lg(sqrt(2^128))或64，并将尝试次数设置为所需的数字（目前为10）来尝试这个168位半素数分解的想法。该脚本可以通过为两个变量PRIMES和TRIALS提供不同的值来轻松测试该方法的当前限制。当前发现的限制是84位素数，这允许分解168位半素数。

Using the Code

测试O((p-q)/2)算法的代码应该可以使用C++编译器编译，并在Linux上的GCC和Windows上的MinGW上进行了测试。运行它需要传入一个半素数。用户会注意到分解所需的运算次数很少，其中两个因子之间存在可数差。按照代码实现，该算法使用了默认的内置32位整数类型。对于pari/GP脚本，您需要先在计算机上安装该软件。然后，您需要编译Java代码来生成随机素数（gen_prime.java）。之后，您就可以运行脚本（test_eulerphi.sh）。代码配置为分解128位半素数。

关注点

目前存在的最优分解算法是广义数域筛法（GNFS）[1]。对于分解更大的数字，建议研究该算法。或者，也许可以基于计算(p + q)或(p – q)（其中n = p * q）的思想发现其他技术。

结论

本文介绍了两种涉及二次公式的技术，其中一种技术旨在利用两个因子之间的差值，而另一种技术能够分解128位以上的半素数。后者的实现作为一个脚本提供，所有代码均可在网上免费获取，供进一步研究和使用。分辨率问题仍然是一个有趣的问题。目前，还没有人推导出一种以多项式时间运行的方法，或者证明分辨率问题的复杂度不在多项式时间[1]。O((p-q)/2)算法的使用在p-q较大的情况下受到限制。n的欧拉Phi的使用之所以受到限制，是因为人们推测计算n的欧拉Phi的难度与分解n的难度相当。

总而言之，使用Pari/GP通过欧拉Phi技术迄今为止分解的最大数字是一个168位整数

parisize = 4000000, primelimit = 500000
factoring: 133508893528006101286190330650870490524366217338949
q: 10226209140199387919889509.00
p: 13055560638123520736792161.00

参考文献

• [1] Pomerance, C. & Crandall, R. (2005) Prime Numbers, Springer, New York.
• [2] Larson, R. E., Hostetler, R. P., Edwards, B. H., & Heyd, D. E. (1997)
• PreCalculus, Houghton Mifflin Company, New York.