Pollard‘s rho因子分解法——C语言实现

本文主要是介绍Pollard‘s rho因子分解法——C语言实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

    Pollard's rho的核心思想其实就是求p和q的倍数，而这样的倍数有无穷多个,当N值很小的时候，成功率还是很高的，当N值很大时，该算法就不灵了。

#include <stdio.h>
#include <stdlib.h>int gcd(int x,int y){int z;while(y){z=x,x=y,y=z%y;}return x;
}int f(int x,int c,int n)
{return (x*x+c)%n;
}int Pollard_Rho(int N)
{//int c=rand()%(N-1)+1;int c = 1;int t=f(0,c,N);int r=f(f(0,c,N),c,N);//两倍速跑while( t!=r ){int d=gcd(abs(t-r),N);if(d>1){printf("d = %lld\n",d);return d;}t=f(t,c,N);r=f(f(r,c,N),c,N);}return N;
}int main() {int n = 70191551;Pollard_Rho(n);return 0;
}

这篇关于Pollard‘s rho因子分解法——C语言实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---