三、对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); }
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; } } }