#include<iostream>
#include<math.h>
#include<ctime>
using namespace std;
#define RUN 100
extern long Randomi(long a,long b);
extern long Extend_EuleGCD(long a,long b);
bool IsPrime( long d) //这是规模变小后的再来判断，所以效率应该会低些
{
for(int i=2;i<(int)sqrt((double)d)+1;i++)
if(0==d%i)
return false;
return true;
}
long Pallard_RHO(long n)
{
long i=1;
long x=Randomi(0,n-1);
long y=x;
long k=2;
long d;
int countRun=(int)pow(n,0.25)+1; //记循环的次数,次数过后,如果没有退出循环，重新再来选择随机种子
while(true&&countRun!=0)
{
srand((unsigned)time(NULL));
countRun--;
x=x*x-1;
x=x%n; //invalidate variable x
long xy=abs(x-y);
d=Extend_EuleGCD(xy,n);
if(d!=1&&d!=n)
{
return d;
}
if(i==k) //count,if i is even number,then save the value of x in y
{
y=x;
k=k*2;
}
}
}
void Print( long d)
{
if(IsPrime(d)&&d!=1)
cout<<d<<" ";
}
int main()
{
long n;
cout<<"Enter the number(Composite) you want to factorize:"<<endl;
cin>>n;
cout<<"the number is compositing……"<<endl;
if(IsPrime(n))
{
cout<<n<<" is Prime!"<<endl;
return 0;
}
long factor=1;
for(int i=0;i<RUN;i++)
{
while(n!=factor) //factor应该肯定在执行过程中为素数
{
factor=Pallard_RHO(n);
while(!IsPrime(factor))
{
factor=Pallard_RHO(factor);
}
Print(factor);
n=n/factor;
if(IsPrime(n))
{
cout<<n<<endl;
break;
}
}
}
return 0;
}
实验8.rar （9个子文件） 
实验8 
实验8.docx 73KB Composite_Factor_Rho 
Composite_Factor_Rho.plg 2KB Randomi.cpp 222B Extend_EuleGCD.cpp 228B Composite_Factor_Rho.dsw 565B main.cpp 1KB Composite_Factor_Rho.ncb 49KB Composite_Factor_Rho.dsp 4KB Composite_Factor_Rho.opt 48KB资源评论
