作业帮C语言 设计并实现一种大素数随机生成方法； 实现一种快速判定任意一个大数是否是素数方法
来源：学生作业帮 编辑：作业帮 分类：综合作业 时间：2024/05/26 16:06:07
C语言 设计并实现一种大素数随机生成方法； 实现一种快速判定任意一个大数是否是素数方法
Rabin -Miller算法是典型的验证一个数字是否为素数的方法.判断素数的方法是Rabin-Miller概率测试,那么他具体的流程是什么呢.假设我们要判断n是不是素数,首先我们必须保证n 是个奇数,那么我们就可以把n 表示为 n = (2^r)*s+1,注意s 也必须是一个奇数.然后我们就要选择一个随机的整数a (1=1;
t=(t*t)%n;
}
return s;
}
//Rabin-Miller素数测试,通过测试返回1,否则返回0.
//n是待测素数.
//注意：通过测试并不一定就是素数,非素数通过测试的概率是1/4
int RabinMillerKnl(unsigned long n)
{
unsigned long b,m,j,v,i;
//先计算出m、j,使得n-1=m*2^j,其中m是正奇数,j是非负整数
m=n-1;
j=0;
while(!(m&1))
{
++j;
m>>=1;
}
//随机取一个b,2
再问： 那产生随机大素数 不是先要产生个大数在判断是否为素数吗 那大数怎么产生 比如我要产生20位内的大数 这怎么弄？
再答： 代码第一段就是拿来生成随机数的 //随机数产生器 //产生m~n之间的一个随机数 unsigned long random(unsigned long m,unsigned long n) { srand((unsigned long)time(NULL)); return(unsigned long)(m+rand()%n); }
再问： 我把代码贴进去根本无法运行啊
再答： 嗯,我没试过,不好意思第一行改为:#include<iostream>第四行加上:using namespace std;调试编译好了,没问题了
截图:
大一点的数运行起来有点慢哦!
t=(t*t)%n;
}
return s;
}
//Rabin-Miller素数测试,通过测试返回1,否则返回0.
//n是待测素数.
//注意：通过测试并不一定就是素数,非素数通过测试的概率是1/4
int RabinMillerKnl(unsigned long n)
{
unsigned long b,m,j,v,i;
//先计算出m、j,使得n-1=m*2^j,其中m是正奇数,j是非负整数
m=n-1;
j=0;
while(!(m&1))
{
++j;
m>>=1;
}
//随机取一个b,2
再问： 那产生随机大素数 不是先要产生个大数在判断是否为素数吗 那大数怎么产生 比如我要产生20位内的大数 这怎么弄？
再答： 代码第一段就是拿来生成随机数的 //随机数产生器 //产生m~n之间的一个随机数 unsigned long random(unsigned long m,unsigned long n) { srand((unsigned long)time(NULL)); return(unsigned long)(m+rand()%n); }
再问： 我把代码贴进去根本无法运行啊
再答： 嗯,我没试过,不好意思第一行改为:#include<iostream>第四行加上:using namespace std;调试编译好了,没问题了
截图:
大一点的数运行起来有点慢哦!