密码学|因子分解算法密码学|数论

分解任意的整数n时，我们自然要寻找n的一个非平凡因子，如要把n分解为素数乘积，可以先用随机素性检测法进行测试，再对不是素数的因子进一步的分解。
那么对RSA的公开模数n，我们如果能找到n的非平凡因子意味着RSA公钥体系的崩塌。当下整数因子分解最快的一般性算法是数域算法（NFS），这个算法在合理假设下期望的运行时间为O（exp（c（logN）^1/3 * （loglogN）^2/3）），这意味着NFS不是多项式算法而是亚指数时间算法。
下面我们来介绍3种典型的因子分解算法，这些算法是对某些特定的大整数为有效的算法，但对绝大多数没有影响，所以不会破坏RSA公钥体系的崩塌，但是同时，这也提醒了我们，在选择RSA的素数或模时要加以小心
一.Pollard “rho”算法
Pollard提出了一个有效的蒙特卡洛方法来寻找大整数的一个非平凡因子，我们称之为Pollard “rho”算法。
我们对要分解的正整数n，选取一个初始值x0，并构造一个适当的函数f，递归计算xi=f（xi-1）mod n，对不同的i，j，利用欧几里得算法计算gcd（xi-xj，n）。如果对某i，j有1 < gcd（xi-xj，n）< n，则意味着找到了n的一个非平凡因子，用这种方法得到的未必是n的最小因子，也未必是素数，甚至找到的可能是n自己，只是概率很小罢了。
注：

{xn}的值会周期性的出现：这是因为Z/nZ是有限集，肯定存在i，j，使得xi≡xj(mod n)，则有f(xi)≡f(xj)(mod n)，即xi+1≡xj+1(mod n)，从而迭代下去，对任意整数d>0，我们有xi+d≡xj+d(mod n)
算法最重要的一步是选取适当的函数f，通常选一个整系数的多项式，如f(x)=x^2+1。如果算法失败的话，我们则选取不同的初始值或者不同的函数f重新运行算法。

伪代码：

Pollard p-方法
input：f，x：= x0
x’：= f(x) modn
p = gcd（x-x’，n）
if p = 1
do x = f(x) mod n
x' = f(x') mod n
p = gcd （x-x’，n）
if p = n
output “失败”
else
output p

代码：

C++参考代码：http://blog.csdn.net/maxichu/article/details/45459533

说明：
上述算法实际是通过计算x2i - xi与n的最大公因子来寻找n的一个因子p，假设对某个i x mod p对于x∈X有至少一次碰撞，若集合X的大小约为1.17p^1/2，根据生日悖论，存在概率的碰撞至少为 50%，以上算法最多循环j（j
设p是n的最小素因子，则用p-方法找到p的期望运行时间为O（n^1/4*(log n)^2）

二.Pollard p-1算法
我们首先给出一个定义：
B-光滑：对于整数n，如果它的所有某个素因数的幂次都<=B，那么称整数n是B-光滑的。
伪代码：

input B （整数n满足B-光滑）
a := 2
for j= 2 to B
do a := a^j mod n
d = gcd (a-1,n)
if 1 output d;
else
output "Error"

算法要求n有一个素因子使得 p-1 只有小的素数幂因子，之久要求构造RSA mod n时，选择的p-1和q-1都含有至少一个大的素数幂因子，从而使上述算法失败，例如可以取p=2p1+1，q=2q1+1，其中p，q，p1，q1都是大素数。
利用平方乘算法计算每一个模指数a^j mod n需要至多2logB个模乘法，而最大公因子的计算时间为O（(log n)^3），因此整个算法的计算复杂度为O（BlogB(logn)^2+(logn)^2）。如果B是logn的多项式，那么这个算法是关于输入n的多项式时间算法。
界B的选取是要考虑的，B越大算法需要时间越长，寻找非平凡因子可能性也越大，选取最小的B的代码详见：http://blog.csdn.net/qq_31917799/article/details/53221033

代码实现：
http://blog.csdn.net/wyf12138/article/details/72983601

三.Dixon随机平方算法
随机平方算法也是一种有效的因子分解方法，其思想是：如果可以找到 x ≡ ± y mod n，使得 x^2 ≡ y^2，则gcd(x+y,n)与gcd(x-y,n)都是n的平凡素因子。不妨设p1，p2，... ，pb为最小的b个素数，B={p1，p2，...，pb}为因子基，假定可以找到c个同余方程（c要求稍大于B）：

文章图片

记

文章图片
，如果c>b，那么a1，a2，...，ac是线性相关的，不妨设为

文章图片
，则有：

文章图片

上式左右两边都是完全平方数，所以可以成功分解n。
特别的，对于上述方法，如果n不是素数幂次， x ≡ ± y mod n 成功的概率最多为50%
注：如何取z使得 z^2 mod n在B上完全分解？
这里有两种方法，一种方法是取z=j+[√kn]，j=0,1，...；k=0,1，...则 z^2 mod n的值很小。另一种方法是取 z=[√kn]，则-z^2 mod n的值很小。这些整数的平方模n后一般比较小，因此比随即选择z在B上完全分解的可能性要更高一点，在后者的情况下，我们将-1添加到因子集B中，就可以在B上分解 z^2 mod n。因子集取得越大则堆积的同余式越多；因子集取的过小，则平方模n后可能不在其上分解。
此算法的计算时间为O（exp( (1+O(1))√(ln n*lnln n) )），目前对于大整数分解最有效的算法就是椭圆曲线分解算法（ECM）和数域筛法（NFS）。
【密码学|因子分解算法】