首页 > 编程语言 > 详细

C++实现Miller-Rabin素数测试

时间:2015-08-10 14:49:58      阅读:294      评论:0      收藏:0      [点我收藏+]

原理参见《离散数学》P201

#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cmath>

using namespace std;

bool Miller_Rabin(long long n)
{
	if(n < 2)
		return false;
	else if(n == 2)
		return true;
	
	long long q = 0, m = n - 1;
	while(m % 2 == 0) {
		m /= 2;
		++q;
	}

	long long a = rand()%(n-2)+2;
	long long x1 = (long long)pow(a, m) % n, x2;

	for(int i = 1; i <= q; ++i) {
		x2 = (x1*x1) % n;
		if(x2 == 1 && x1 != 1 && x1 != n-1)
			return false;
		x1 = x2;
	}

	if(x2 != 1)
		return false;
	else
		return true;
}


int main(void) 
{
	srand((unsigned)time(NULL));
	long long num;
	while(cin >> num) {
		if(num > 1) {
			if(Miller_Rabin(num))
				cout << "true" << endl;
			else
				cout << "false" << endl;
		}
	}

	return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

C++实现Miller-Rabin素数测试

原文:http://blog.csdn.net/qq_21555605/article/details/47398097

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!