milrab.cpp

初学密码内容

#include <iostream.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <conio.h>

long double FitForMod(long double a, long double b)		//long double类型的两个数(a,b)求模的运算
{														//但a,b的值范围可用unsigned long表示
	unsigned long ultmpa, ultmpb;
	ultmpa = (unsigned long) a;
	ultmpb = (unsigned long) b;

	return (long double) (ultmpa % ultmpb);
}

long double powModldb(long double a, long double q, long double n)	//求pow(a, q)%n的函数
{												//因为long double不可以直接运算%
												//此函数把pow(a, q)尽量减小，再用FitForMod求出
	long double tmod, k=0, value=1, tval=1 ;	//利用性质:p1*p2 mod n = (p1 mod n)*(p2 mod n) mod n
												//tmod为(pi mod n), k为记数, value为最终值, tval为pi
	while( tval*a<pow(10, 9) && q>0)			
	{											//tval属于unsigned long范围 tval = pow(a, k)
		tval *= a;								//且：pow(a, q) = tval * pow(a, q-k)
		k++;									//注意：注释写的q为原q
		q--;
	}
	value = tmod = FitForMod(tval, n);			//求出tmod 即 tval mod n

	while(q > k)								//即：pow(a, q) = tval*tval*...*tval*pow(a, q-i*k)
	{											//i为tval的个数		
		value = FitForMod(value*tmod, n);
		q -= k;
	}
	
	if(q > 0)									//处理pow(a, q-ik)
	{
		tmod = FitForMod(pow(a, q), n);
		value = FitForMod(value*tmod, n);
	}

	return value;								//成功返回
}

//**************Miller&Rabin算法****************//

bool TestIfPrime(long double n, int tt)		//测试n是否为素数的函数
{											//输入：待测数n，测试次数tt
	long double k=0;						//输出：返回值为true表示n为素数，否则为合数
	long double q = n-1;
	long double a;			
	unsigned long ultmp;					//用来暂存unsigned long类型的数
	bool maybe=false;						//maybe为true时表示该数为素数，否则为合数

	while(1)								//求出q和k，使n-1 = pow(2, k)*q;
	{
		if( FitForMod(q, 2) != 0 ) break;
		else{
			q = q / 2;
			k++;
		}
	}

	srand((unsigned)time( NULL ));
	for(int i=0; i<tt; i++)					//开始测试过程
	{
		cout<<endl<<"第 "<<i+1<<" 次测试"<<endl;
		ultmp = (n>4294967294)? 4294967294:(unsigned long)n;
												//ultmp取Min(4294967294, n);
		a = rand()%(ultmp-1) + 1;				//随机产生一个1~ultmp-1的数a
		cout<<"k="<<k<<"   q="<<q<<"   a="<<a<<endl;
		cout<<"pow1 = "<<(long double)pow(a, q)<<endl;
		cout<<"pow1 mod n = "<<powModldb(a, q, n)<<endl;
		if( powModldb(a, q, n) != 1 )			//下面是核心算法见Miller&Rabin
		{
			cout<<"---IN L1---"<<endl;
			for(long double j=0; j<k; j++)
			{
				cout<<"pow2 = "<<(long double)pow(a, pow(2, j) * q)<<endl;
				cout<<"pow2 mod n = "<<powModldb(a, pow(2, j) * q, n)<<endl;
				if(powModldb(a, pow(2, j) * q, n) == n-1)
				{
					cout<<"===IN L2==="<<endl;
					maybe = true;				//可能为素数
					break;
				}
			}
			if(!maybe) return false;			//一定为合数
		}
	}
	return true;
	
}

/***********************DEMO***************************/
void main()										//显示程序
{
	long double n;								//待测数n
	int tt;										//测试次数

	cout<<"***正在运行测试一个数是否为素数显示程序***"<<endl<<endl;
	cout<<"请输入要测试的数：";
	cin>>n;
	cout<<endl<<"测试次数：";
	cin>>tt;

	if(	TestIfPrime(n, tt) )	cout<<endl<<"此数是素数!"<<endl;
	else						cout<<endl<<"此数是合数!"<<endl;
	cout<<"Press any key to Quit "<<endl;
	getch();
}