赞赏码 & 联系方式 & 个人闲话
【实验名称】Miller-Rabin算法
【实验目的】
1、理解Miller-Rabin算法的数学原理；
2、通过实验掌握Miller-Rabin素数判定的算法。
【实验原理】
Miller-Rabin算法是目前主流的基于概率的素数测试算法，在构建密码安全体系中占有重要的地位。
基本原理：令n表示一个整数，假设存在整数x和y满足x2 ≡ y2(mod n)，但x≠ ±y(mod n),那么n是合数。而且gcd(x-y,n)给出了n的一个非平凡因子。
Miller-Rabin素数判定: (n-1=2km，m为奇数)，如果对所有的r∈[0,k-1]，若am mod n≠1且a^(2^r m) mod n≠-1，则n是合数。
【实验内容】
实验内容： 编程实现Miller-Rabin素数判定算法，并判断23456789是否是素数？
代码：（代码解释见代码中注释）
//现代密码学实验4 Miller_Rabin算法
#include<stdio.h>
#include <stdlib.h>
#include <time.h>
#include<math.h>
#define LL long long//幂次运算，含模运算，防止溢出
LL My_Pow(LL a, LL m, LL input)
{LL result = 1;for (int i = 0; i < m; i++){result = (result*a) % input;}return result;
}//Miller_Rabin算法
int Miller_Rabin(LL input)
{if (input == 2 || input == 3){//2、3特判为素数return 1;}else if (input % 2 == 0 || input == 1){//偶数和1特判为非素数return -1;}else{int ji = 0;LL b;LL m = input - 1;//计算k,即jiwhile (m % 2 == 0){m = m / 2;ji++;}srand(time(NULL));LL a = 0;//随机取awhile (a <= 1){a = rand() % (input - 1);}b = My_Pow(a, m, input);//若b0=1或-1if (b == 1 || b == input - 1){return 1;}else{double r = 0;for (r = 0;; ){//循环直到r<k-1r++;LL temp1 = LL(m*(pow(2, r)));LL temp = My_Pow(a, temp1, input);if (temp == input - 1){//等于-1则为素数return 1;}else if (temp == 1){//等于1一定为合数return -1;}else{if (r < ji - 1){//都不等于则继续continue;}else{//达到次数则返回该数为合数return -1;}}}}}
}int main()
{printf("****************************************\n");printf("*** 欢迎来到素数判断器 ***\n");printf("***1.输入一个数判断是否为素数 ***\n");printf("***2.输入一个数输出这个数内的素数 ***\n");printf("***3.退出程序 ***\n");printf("****************************************\n\n");int judge;while (true){printf("请选择功能：");scanf("%d", &judge);if (judge == 1){//输入一个数判断是否为素数LL input;printf("请输入待判断的整数：");scanf("%lld", &input);int flag = 1;for (int i = 0; i < 10; i++){if (Miller_Rabin(input) == -1){flag = -1;break;}}if (flag == 1){printf("%lld是素数\n\n", input);}else{printf("%lld不是素数\n\n", input);}}else if(judge==2){//输入一个数输出这个数内的素数printf("你想求多少以内的素数：");LL number;scanf("%lld", &number);for (LL i = 2; i <= number; i++){int flag = 1;for (int j = 0; j < 10; j++){if (Miller_Rabin(i) == -1){flag = -1;break;}}if (flag == 1){printf("%lld ", i);}}printf("\n\n");}else if (judge == 3){//退出printf("退出成功！\n");break;}}return 0;
}
运行演示：
【小结或讨论】
这次算法比起上次的AES可以说是简单很多了，只是完成RSA算法的一部分——用于素数判断的Miller-Rabin算法。这次的实验让我重新认识了素数判定，原本我只知道那种遍历到
基础算法，没想到还可以根据费马小定理来进行这种概率性素数判断，感到十分新鲜。
坦诚地说，虽然算法并不复杂，但是其背后的数学原理确实是有些晦涩难懂的。书中在这提出了一个新的“基本定理”和信息安全数学基础中的“费马小定理”，并把其结合成Miller-Rabin素数判定算法。这一块书上写的的解释和证明，我觉得略微简略了一点，看起来比较费劲，特别是第一个b0和第二个b1的mod n的结果判断比较难懂，两者一个都用了费马小定理，另一个“1”时用的是基本定理、“-1”时用的是费马小定理。但是只要把解释看懂了，整个算法也就比较明白了。
看懂了后，在算法实现的过程中我觉得还有两个小坑吧。一个当然就是幂次运算的溢出，由于C语言的模运算%限制必须要是整型，而整型最大的就是long long型，这对于大数幂次运算是远远不够的，所以我自己写了个My_Pow幂次运算，每次乘法都mod n这样就能解决溢出问题；其次还有一个就是算法中mod运算结果-1应该是n-1，因为按My_Pow算的话保持数是正数，那么在模运算中-1也就等于n-1了，这是我觉得要注意的两点。