Miller Robin素数测试与Pollcard Rho因数分解


		<1>预备算法
[cpp] 
LL mul(LL a, LL b, LL p)  
{  
     LL rn=0, i;  
     for(i=1; i<=b; i<<=1,a=(a+a)%p)  
      if(b&i) rn=(rn+a)%p;  
     return rn;  
} // 计算模意义下两大数乘积  
LL ksm(LL a, LL b, LL p)  
{  
     LL rn=1;  
     for(; b; a=mul(a,a,p),b>>=1)  
      if(b&1) rn=mul(rn,a,p);  
     return rn;  
} // 计算模意义下两大数乘方  
LL gcd(LL a, LL b)   
{   
     LL tmp; if(a<b) tmp=a,a=b,b=tmp;  
     while(b) tmp=a%b, a=b, b=tmp;  
     return a;  
} // 求最大公约数  
 
<2>Miller Robin素数测试
能在(0.25)^S的错误率下判定质数，相应地需要付出(S*log n)的时间复杂度。
原理基于两个定理：
1.若p是质数，0<a<p，那么a^(p-1)≡1(mod p)。
2.对于0<x<p，x^2≡1(mod p) 有且只有两解： x=1和x=p-1。
[cpp] 
bool isprime(LL n)  
{  
     if(n==2) return true;  
     if(n<2 || !(n&1)) return false;  
     LL a,x,y, u=n-1; int t=0;  
     while((u&1)==0) t++, u>>=1;  
     for(i=0; i<S; i++)  
     {  
      a=rand()%(n-1)+1;  
      x=ksm(a,u,n);  
      for(int j=1; j<=t; j++)  
      {  
           y=mul(x,x,n);  
           if(y==1 && x!=1 && x!=n-1) return false;  
           x=y;  
      }  
      if(x!=1) return false;  
     }  
     return true;  
}  
 
 
<3>Pollcard Rho因数分解
复杂度貌似是n^(1/4)，这应该是因数分解的最快算法了。
[cpp] 
void rho(LL n)  
{  
     if(isprime(n)) { list[++top]=n; return; }  
     LL a,x,y,z,p;  
     while(true)  
     {  
      for(x=1,y=1,z=rand()+1,p=1; p==1; )  
      {  www.zzzyk.com
           y = (mul(y,y,n)+z)%n;  
           p = gcd((x-y+n)%n,n);  
           x = (mul(x,x,n)+z)%n;  
           y = (mul(y,y,n)+z)%n;  
      }  
      if(p==n) continue;  
      rho(p); rho(n/p);  
      return;  
     }  
}  
正确性是显然的，复杂度分析么——总之很快。

补充：软件开发 , C++ ,