beloved_ACM

SB,NB,都是一个B.
posts - 29, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

MILLER-RABIN和大数因子分解

Posted on 2011-09-02 11:12 成幸毅 阅读(441) 评论(0)  编辑 收藏 引用
#include <iostream>
#include 
<cstdio>
#include 
<cstring>
#include 
<cmath>
#include 
<cstdlib>
#include 
<algorithm>
using namespace std;
const int maxn = 1100;
typedef  __int64 bigint;
bigint gcd(bigint A,bigint B)
{
    
while(B)
    
{
        bigint C 
= A%B;
        A 
= B;
        B 
= C;
    }

    
return A;
}

bigint product_mod(bigint A,bigint B,bigint C)
{
    bigint R 
= 0,D = A;
    
while(B)
    
{
        
if(B&1)
        
{
            R 
= (R+D);
            
if(R>C)  R -= C;
        }

        D 
+= D;
        
if(D>C)  D -= C;
        B 
>>= 1;
    }

    
return R;
}

bigint power_mod(bigint A,bigint B,bigint C)
{
    bigint R 
= 1,D = A;
    
while(B)
    
{
        
if(B&1)  R = product_mod(R,D,C);
        D 
= product_mod(D,D,C);
        B 
>>= 1;
    }

    
return R;
}

int pri[] = {2,3,5,7,11,13,17,19,23,29};
bool Miller_Rabin(bigint n)
{
    
if(n<2)  return false;
    
if(n==2)  return true;
    
if(!(n&1))  return false;
    bigint k 
= 0,i,j,m,a;
    m 
= n-1;
    
while(!(m&1))  m = (m>>1),k++;
    
for(i=0;i<10;i++)
    
{
        
if(pri[i]>=n)  return true;
        a 
= power_mod(pri[i],m,n);
        
if(a==1)  continue;
        
for(j=0;j<k;j++)
        
{
            
if(a==n-1)  break;
            a 
= product_mod(a,a,n);
        }

        
if(j==k)  return false;
    }

    
return true;
}

bigint pollard_rho(bigint C,bigint N)
{
    bigint I,X,Y,K,D;
    I 
= 1;
    X
=Y=rand()%N;
    K 
= 2;
    
do{
        I
++;
        D 
= gcd(N+Y-X,N);
        
if(D>1&&D<N)  return D;
        
if(I==K)  Y=X,K<<=1;
        X
=(product_mod(X,X,N)+N-C)%N;
    }
while(Y!=X);
    
return N;
}

bigint allFactor[maxn];
int fn;
void rho(bigint N)
{
    
if(Miller_Rabin(N))
    
{
        allFactor[
++fn]=N;
        
return ;
    }

    bigint T 
= N;
    
while(T>=N) T = pollard_rho(rand()%(N-1)+1,N);
    rho(T);
    rho(N
/T);
}

int main()
{
    bigint n;
    
while(true)
    
{
        scanf(
"%I64d",&n);
        
if(n<=0)  break;
        
if(Miller_Rabin(n))   printf("    %I64d\n",n);
        
else
        
{
            fn
=0;
            rho(n);
            sort(allFactor
+1,allFactor+fn+1);
            
for(int i=1;i<=fn;i++)
            
{
                printf(
"    %I64d\n",allFactor[i]);
            }

        }

        cout
<<endl;
    }

    
return 0;
}



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理