primer.h

随机算法实现

#include<iostream.h>
#include <time.h>
#include<stdlib.h>
#include<string>


using namespace std;


string reverse(string a)
{
    int l =a.size();
	string res ;
	for(int i=l-1; i>=0; i--)
	{
		res = res + a[i];
	}

	return res;

}


string convert(int a)
{
  string s;
  int x;
  while(a!=0)
  {
    x=a%2;//余数
    a=a/2;//商
	if(x==1) s=s+'1';
	else s=s+'0';

  }
  return reverse(s);
}

int expmod(int a,int m,int n)//求am mod n
{
int c;
string str=convert(m);

for(int i=str.size();i>=0;i--) 
{
c=c*c%n;
if(str[i]=='1') c=a*c%n;
}
return c;

	

}


bool witness(int a,int n,int &q,int &m) //素数判定
{
int x=expmod(a,m,n);
if(x==1) return false;

for(int i=1;i<=q;i++)
{
if(x==n-1) return false;
x=x*x%n;

if(x==1)  return true;

}
return true;


}

int random_num(int n)//产生随机数2~n-2
{

    time_t t;     
    srand((unsigned) time(&t)); 
    return rand() % (n-4)+2; 
}

void comp(int n,int &q,int &m)     //求出q,m，使得n-1=m*2(q)
{
q=m=0;

while(n%2==0)
{
q++;
n/=2;
}
m=n;

}



bool miller_rabin(int n)              //返回为真是合数
                               
{
int randnum;

int q,m;
int times;        
if(n%2==0)     return true;

comp(n-1,q,m);                        //求出q,m，使得n-1=m*2(q)

while(times--)                        //共做times次判定

{
 randnum=random_num(n);               //产生随机数2~n-2
 
 if(witness(randnum,n,q,m))  return true;  
}
return false;


}