mb.h

此代码实现的功能主要是做素性判断的MillerRobin测试

#include <time.h>
#include <stdlib.h>
#include "stdio.h"
bool Btest(int a,int i)//i-1=2^s*t
{
	 int s=0,j;
	 int x=1;
	 int t=i-1;   //t is an even
	 do{
	 s++;
	 t=t/2;
	 }while(t%2==1);
	 for(j=1;j<=t;j++)
	 {
		x=(x*a)%i;
	 }
	 if((x==1)||(x==(i-1)))
	return true;
	 for(j=1;j<=s-1;j++)
	 {
		 x=(x*x)%i;
		 if(x==(i-1))
			 return true;
	 }
	 return false;

}
bool MB(int i)
{
	int a;
	time_t t;
	srand((unsigned) time(&t)*10000000);
	a=rand()%(i-3)+2;
	return Btest(a,i);
	
}
bool RepeatMB(int i,int j)
{
	int k;
	for(k=1;k<=j;k++)
		if (MB(i)==false)
			return false ;
	return true;
}