Miller Rabbin测试素数

【补充】以前代码优点问题,在 Modular_Exp 函数里,最后 ans 忘了 return,已修正! 2013-05-29

伪素数:如果n是一个正整数,如果存在和n互素的正整数a满足a^n-1≡1(mod n),我们说n是基于a的伪素数。如果一个数是伪素数,它几乎肯定是素数。(即下面的费马小定理)
费马小定理是数论中的一个重要定理,其内容为: 假如p是质数,且(a,p)=1,那么 a^(p-1) ≡1(mod p) 假如p是质数,且a,p互质,那么 a的(p-1)次方除以p的余数恒等于1。
更多关于费马小定理请参阅:
http://baike.baidu.com/view/263807.htm?fr=ala0_1


这是Miller Rabbin测试素数的代码模版:

[code lang=”cpp”]
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define maxTest 100

long long int Random(long long int n)
{
return (long long int)((double)rand()/RAND_MAX*n+0.5);
}

long long int Modular_Exp(long long int a, long long int b, long long int n) // a^b mod n
{
long long int ans;
if(b == 0)
return 1;
if(b == 1)
return a % n;
ans = Modular_Exp(a, b/2, n);
ans = ans * ans % n;
if(b % 2)
ans = ans * a % n;
return ans;
}

bool Miller_Rabbin(long long int n)
{
for(int i=1; i<=maxTest; ++i)
{
long long int a = Random(n-2)+1;
if(Modular_Exp(a, n-1, n) != 1)
return false;
}
return true;
}

int main()
{

srand(time(NULL));
long long int n;

while(scanf("%lld", &n) == 1) {
if(Miller_Rabbin(n))
printf("Primer\n\n");
else
printf("Not Prime\n\n");
}

return 0;
}

[/code]

注:
1.Modular_Exp函数详细见:
快速幂取模(点击查看)
2.这个算法是概率型算法,而不是确定型算法。不过多次运行后出错概率很小,在实际应用中是可以信赖的。

感谢rakerichard小牛的资料和刘汝佳老师的黑书。

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《Miller Rabbin测试素数》有6个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注