ComSec作业一:Miller-Rabin算法---编程题
2021/10/3 1:10:31
本文主要是介绍ComSec作业一:Miller-Rabin算法---编程题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Miller-Rabin算法
算法的理论基础:
- Fermat定理:若n是奇素数,a是任意正整数(1≤ a≤ n−1),则 a^(n-1) ≡ 1 mod n。
- 推演自Fermat定理, 如果n是一个奇素数,将n−1表示成2^s*r 的形式,r是奇数,a与n是互素的任何随机整数,那么a^r ≡ 1 mod n或者对某个j (0 ≤ j≤ s−1, j∈Z) 等式a^(2jr) ≡ −1 mod n 成立。
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <map> using namespace std; const int times = 20; int number = 0; map<long long, int>m; 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 )//用检验算子a来检验n是不是素数 { long long tem = n - 1; int j = 0; while(tem % 2 == 0) { tem /= 2; j++; } long long x = q_pow( a, tem, n ); if(x == 1 || x == n - 1) return true; while(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 || n % 2 == 0) return false; for(int i = 1; i <= times; i++) { long long a = Random( n - 2 ) + 1; if(!witness( a, n )) return false; } return true; } int main( ) { long long tar; while(cin >> tar) { if(miller_rabin( tar )) cout << "Yes, Prime!" << endl; else cout << "No, not prime.." << endl; } return 0; }
这篇关于ComSec作业一:Miller-Rabin算法---编程题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享