没有合适的资源?快使用搜索试试~ 我知道了~
Miller-Rabin素性测试算法
5星 · 超过95%的资源 需积分: 49 34 下载量 68 浏览量
2010-05-21
10:16:39
上传
评论
收藏 833B TXT 举报
温馨提示
试读
2页
miller - rabin 素性测试,是做rsa算法的重要组成部分
资源推荐
资源详情
资源评论
#include <stdio.h>
#include <math.h>
int mod(int i,int d,int n)//模n的大数幂乘快速算法
{
int c = 1;//c为余数,保存每次模后的数
while(d == 0)
{
if(d % 2 == 0){d = d / 2;i = (i * i) % n;}//d是偶数,就先求i平方的模
else {d--;c = (c * i) % n;}//d是奇数,就与上一次的模相乘后在求模
}
return c;//d为0,只能通过d--,所以返回的必是c
}
void main()
{
int i = 2,d,n = 78779;
d = n - 1;
while(d != 1)
{
if(mod(i,d,n) == 1)
{
if(d % 2 != 0){printf("是素数"); break;} //如果是d奇数就结束
d = d / 2;
if(mod(i,d,n) == n - 1){printf("是素数");break;} //如果模为n-1也结束,因为只有当模为1时才能不断地把d折半
}
else {printf(" 不是素数");printf("%d",mod(i,d,n));break;}//如果在d折半的过程中出现的mod不是1或n-1的话就结束
}
#include <math.h>
int mod(int i,int d,int n)//模n的大数幂乘快速算法
{
int c = 1;//c为余数,保存每次模后的数
while(d == 0)
{
if(d % 2 == 0){d = d / 2;i = (i * i) % n;}//d是偶数,就先求i平方的模
else {d--;c = (c * i) % n;}//d是奇数,就与上一次的模相乘后在求模
}
return c;//d为0,只能通过d--,所以返回的必是c
}
void main()
{
int i = 2,d,n = 78779;
d = n - 1;
while(d != 1)
{
if(mod(i,d,n) == 1)
{
if(d % 2 != 0){printf("是素数"); break;} //如果是d奇数就结束
d = d / 2;
if(mod(i,d,n) == n - 1){printf("是素数");break;} //如果模为n-1也结束,因为只有当模为1时才能不断地把d折半
}
else {printf(" 不是素数");printf("%d",mod(i,d,n));break;}//如果在d折半的过程中出现的mod不是1或n-1的话就结束
}
资源评论
- hang18882013-04-17感觉没有从这个收获到什么 不知道为什么楼上会有一目了然的感觉 呵呵~
- shenjunstar2012-11-01看课本上的例子不是很懂,浏览楼主的RSA算法再结合书上的原理就一目了然了
killerleader
- 粉丝: 3
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功