prime.cpp

RSA加密中的大整数运算

#define SIZE 100000000
char p[SIZE];
unsigned __int64 prime(unsigned __int64 n)
{
	unsigned __int64 t=0; 
	unsigned __int64 mark=10;
	while(mark*mark<n)mark*=10;
	for(unsigned __int64 i=2;i*i<n;i++)
		if(!p[i])
		for(unsigned __int64 j=2;j*i<n;j++)
		{
					p[i*j]=1;
					if(i*j>mark)break;
		}
       
				unsigned __int64 result=n,cp=n;

	   for(i=2;i<mark;i++)
	   {
		   if(!p[i]&&cp%i==0)
		   {
			   result=result/i*(i-1);
			   while(cp%i==0)
				   cp/=i;
		   }
		   
	   }
   if(cp!=1)result=result/cp*(cp-1);

  // printf("%I64d\n",result);
   return result;

}
int gcd(int i,int j)  //i>j
{
	int k=i%j;
	while(1)
	{
	  i=j;
	  j=k;
	  if(j==0)break;
	  k=i%j;
	}
	return i;
}
string an(int n)
{
	
	int p=(int)prime(n);
	int *q=new int[n];
	int mark=0;
	int j=0,t,k;
	for(int i=1;i<n;i++)
	{
		j=0;
		t=i;
		if(gcd(n,i)!=1)continue;
      while(1)
	  {
		  t=1;
		  j++;
		  for(k=0;k<j;k++)t=t*i%n;
		  
	  if(t==1)break;
	  }

	  if(j==p)q[mark++]=i;
	}
        string result="\0";
         char buf[30];
	
	for(i=0;i<mark;i++)
         {
             strcpy(buf,"\0");
             _itoa(q[i],buf,10);
             result=result+buf+"  ";
          }
		//cout<<q[i]<<endl;
return result;

}
/*

void main()
{
//	prime(100);
    an(2);

}*/