|
#2
songls2018-01-06 16:59
三、对pollard rho改造
由于pollrad rho分解算法只对一个数进行判断是否存在n的因子，可以使用上述算法对pollrad rho进行改造，让其在一段范围内进行查找n的因子，提高一定的效率，当然如果改造有什么问题，欢迎大家指正，谢谢！ 先看一下，原始的pollrad rho算法： long Pollard_rho(long n, int c) { long i, k, x, y, d; srand(time(NULL)); i = 1; k = 2; x = rand() % n; y = x; while (true) { i++; x = (mod_mult(x, x, n) + c) % n; d = gcd(y - x, n); if (d > 1 && d < n) return d; if (y == x) /*该数已经出现过,直接返回即可 */ return n; if (i == k) { y = x; k = k << 1; } } } 主要改造在： d = gcd(y - x, n); 先按上述算法写一个函数“ long getfac( long a, long n,int num) { long t; long res,b; int i,m; b=(a*a)%n; t=sqrt(b); if( (t*t)==b && (b*b) != a ) return gcd(a+b,n); res=b; m=1; for( i=0 ; i<num ; i++) { b=b-m; res=(res*b)%n; if( res == 0 ) return gcd( b , n ); m=m+2; } return gcd(res,n); } 改造后的Porllard_rho算法: long Pollard_rho(long n, int c, int num) { long i, k, x, y, d; srand(time(NULL)); i = 1; k = 2; x = rand() % n; y = x; while (true) { i++; x = (mod_mult(x, x, n) + c) % n; /*d = gcd(y - x, n);*/ d=getfac( y-x,n,num); if (d > 1 && d < n) return d; if (y == x) /*该数已经出现过,直接返回即可 */ return n; if (i == k) { y = x; k = k << 1; } } } 在Pollard_rho函数中，加入一个次数的传入值，把d = gcd(y - x, n);修改为d=getfac( y-x,n,num);，既不改变Pollrad rho原先的判断，而且增加了一段范围的判断。 |
一个分解整数的算法
在介绍算法前，先介绍一下原理。
①、设a≡b(mod n)，如果(a，n)=c>1，那么(b，n)=c>1，或者如果(b，n)=c>1，则(a，n)=c>1。
证明: ∵a≡b(mod n) => a-jn=b，j≥0
又 ∵(a，n)=c>1 => a=cf，n=cg (f,g≥1)
∴ 代入上式得:
cf-jcg=b => c(f-jg)=b，即(b，n)=c>1
证毕
反之也然，证明略。
②、对于一组数f1、f2、f3… fm，m≥1，如果其中有一个数fi (i≥1)与n有因子c，即(fi，n)=c≥1，则这组数的乘积:f1*f2*…fi…*fm与n也有因子c，
这是因为f1*f2*…fi…*fm=f1*f2*…cg…*fm=c(f1*f2*…g…*fm)，这里fi=cg。
③、设a^2≡b(mod n)，以a为中心，向两边从1到m进行加减(m≥1)的一组平方剩余可以表示如下:
(a-m)^2≡dm，…，(a-3)^2≡d3，(a-2)^2≡d2，…(a-1)^2≡d1，a^2≡b，(a+1)^2≡c1，(a+2)^2≡c2，(a+3)^2≡c3，…，(a+m)^2≡cm (mod n)
这组平方剩余的左边相乘可得:
(a-m)^2*…*(a-3)^2*(a-2)^2*(a-1)^2*a^2*(a+1)^2*(a+2)^2*(a+3)^2*…*(a+m)^2 (mod n)
上述乘积中，对a两边的平方剩余进行两两相乘可以得到:
(a-1)^2*(a+1)^2 (mod n)=(a^2-1)^2 (mod n)≡(b-1)^2 (mod n) =>
(a-2)^2*(a+2)^2 (mod n)=(a^2-4)^2 (mod n)≡(b-4)^2 (mod n) =>
(a-3)^2*(a+3)^2 (mod n)=(a^2-9)^2 (mod n)≡(b-9)^2 (mod n) =>
.
.
.
(a-m)^2*(a+m)^2 (mod n)=(a^2-m^2)^2 (mod n)≡(b-m^2)^2 (mod n)
即上述平方剩余左边相乘，可以表达如下:
(a-m)^2*…*(a-3)^2*(a-2)^2*(a-1)^2*a^2*(a+1)^2*(a+2)^2*(a+3)^2*…*(a+m)^2 (mod n)=
a^2*(a^2-1)^2*(a^2-4)^2*(a^3-9)^2*…*(a^2-m^2)^2 (mod n)≡
(a(b-1)(b-4)(b-9)…(b-m^2))^2 (mod
根据②可得，以a为中心向两边加减m的平方剩余中，如果a-i或者a+i(1≤i≤m)含有n的因子c，则上述平方剩余的乘法也必有n的因子c，也即:
a(b-1)(b-4)(b-9)…(b-m^2)必有n的因子c 又根据①，上式可表示为:
b(b-1)(b-4)(b-9)…(b-m^2)
即该乘积中如果有n的因子，上述平方剩余也必有n的因子，共有2m+1个数。
④、对于平方数，可知:
1^2=1
2^2=1+3
3^2=1+3+5
.
.
.
m^2=1+3+5+…+2m-1 (m≥1)
该证明请参考其它文章。
二、算法介绍
根据以上介绍，设计出以下的一个分解算法，供大家参考:
算法:
以a^2≡b (mod n)为基础 输入a，b，n，num
1、if sqrt(b)是平方数 then return gcd(a+sqrt(b)，n)
2、res=b 乘积结果
3、m=1 从1开始计算平方
4、i=1
5、b=b-m 计算下一个减的平方
6、res=(res*b)%n 按③中求乘积
7、if res=0 then return gcd(b，n) 如果为0，b中必有n的因子
8、m=m+2 按④中求平方
9、i=i+1
10、if i<num then goto 5
11、return gcd(res，n)
其中gcd为碾转相除法。
上述算法中，a^2≡b (mod n)选择比较重要，又因算法中使用加2来求平方，速度会受影响，是否还有其它更好的办法来提高速度，或者更好的建议，希望大家多多提出，本人不胜感激。