素数判定Miller_Rabin 算法详解

2021-02-18 06:18

阅读：732

标签：代码 dom 乘法详解基础 string math 复杂度根据

最简单直观简单的素数判定方法就是试除法。对于判断数n是否是素数，我们从2开始一直到sqrt(n)。如果找到一个因子则判断n不是素数，否则是素数。代码如下：

bool isPrime( long long n )
{
    for(long long i = 2; i*i

如果要找到成1~n的所有素数那么这个时间代价就变为O(n^2)，很多时候是不可接受的。
所以随着学习的深入，我们了解到了素数筛法，即从2开始，2的倍数肯定不是素数，再向右扫描，如果扫描到素数，则重复之前的过程，剔除之后的部分合数（准确的说是关于当前质数的倍数），如果扫描到合数则跳过（表示前面已经更新过这个数不是素数）。然后都扫描一遍即可把1~n的素数求解出来。这个算法的复杂度略高于O(n)。素数筛代码如下：

bool isprime[MAXN];
int prime[MAXN];
int cnt = 0;//保存素数个数
void getPrime()
{
	for(int i = 1; i

但是这个算法的弊端在于，为了判断一个大数是否是素数必须从从头开始扫描，而且空间代价也受不了，故不能离散的判断。

Miller_rabin算法

算法的理论基础：

1. Fermat定理：

若n是奇素数，a是任意正整数(1≤ a≤ n−1)，技术图片

证明：由费马定理，可以排除大部分非素数的情况（满足费马定理是素数的必要条件），给出一个奇素数n，显然n-1为一个偶数，存在技术图片 ,显然（q，m为任意整数）是成立的，所以,显然.

2. 二次探测定理：

技术图片

　　证明过程如下：

　　技术图片

　　由p为一个素数可以推出技术图片。

　　所以根据二次探测定理，可以推断技术图片 ,……,.

3. 综上：

对于一个大数n，判断n是不是素数的时候，可以先考虑a^（n-1）≡ 1（mod n）

对于n-1，一定可以拆分成2^s+d：

技术图片

可以从x = a^d开始，依次平方s次，每次平方的时候模上n，按照之前的平方根定理，如果模上n的结果为1的话，那么x一定是1，或者是n-1，如果不满足则不是素数，x=x²，再次循环。

每次随机选一个在2-n-1的数字作为a，可以重复测试。

由于mod上的是n，n是一个大数，所以快速幂中的乘法，需要用快速加法来实现。不然就算模上之后再相乘也会溢出。

代码：

#include  
#include  
#include   
#include   
#include   
#include   
using namespace std;
 
const int times = 20;
int number = 0;
 
mapm;
long long Random( long long n )			
//生成[ 0 , n ]的随机数
{
	return ((double)rand( ) / RAND_MAX*n + 0.5);
}
 
long long q_mul( long long a, long long b, long long mod ) 
{//快速计算 (a*b) % mod
	long long ans = 0;
	while(b)
	{
		if(b & 1)
		{
			b--;
			ans =(ans+ a)%mod;
		}
		b /= 2;
		a = (a + a) % mod;
 
	}
	return ans;
}
 
long long q_pow( long long a, long long b, long long mod ) 
{//快速计算 (a^b) % mod
	long long ans = 1;
	while(b)
	{
		if(b & 1)
		{
			ans = q_mul( ans, a, mod );
		}
		b /= 2;
		a = q_mul( a, a, mod );
	}
	return ans;
}
 
bool witness( long long a, long long n )//miller_rabin算法的精华
{//用检验算子a来检验n是不是素数
	long long tem = n - 1;
	int j = 0;
	while(tem % 2 == 0)
	{
		tem /= 2;
		j++;
	}
	//将n-1拆分为a^r * s
 
	long long x = q_pow( a, tem, n ); 
	//得到a^r mod n
	if(x == 1 || x == n - 1) return true;	
	//余数为1则为素数
	while(j--) //否则试验条件2看是否有满足的 j
	{
		x = q_mul( x, x, n );
		if(x == n - 1) return true;
	}
	return false;
}
 
bool miller_rabin( long long n )  
{//检验n是否是素数
 
	if(n == 2)
		return true;
	if(n 2的偶数则不是素数
 
	for(int i = 1; i > tar)
	{
		if(miller_rabin( tar ))	//检验tar是不是素数
			cout

部分参考：https://www.cnblogs.com/fzl194/p/9046117.html

素数判定Miller_Rabin 算法详解

标签：代码 dom 乘法详解基础 string math 复杂度根据

原文地址：https://www.cnblogs.com/jaszzz/p/12693251.html

上一篇：父类数组如何向下转型

下一篇：推荐算法-协同过滤推荐算法

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：素数判定Miller_Rabin 算法详解
文章链接：http://soscw.com/index.php/essay/56918.html

亲，登录后才可以留言！

素数判定Miller_Rabin 算法详解

Miller_rabin算法

算法的理论基础：

1. Fermat定理：

2. 二次探测定理：

3. 综上：

代码：

评论

热门文章

推荐文章

最新文章

置顶文章