米勒-拉宾算法:快速判断一个数是不是素数
需要用到的定理:
最小费马定理:如果n是素数,则(a ^ (n - 1)) % n恒等于1。
快速模取幂
米勒-拉宾算法就是结合上面两种,通过不断判断fmod(a, n - 1, n)的值是否为1来判断。这是一个概率算法,如果为1,不一定为素数,不为1,则必定是合数。循环判断多次就会让概率变得极为的小。
算法模板:
#include <iostream>
using namespace std;
int fmod(int a, int b, int c)//快速模取幂
{
if(b == 1) return a;
int t = fmod(a, b / 2, c);
t = (t * t) % c;
if(b & 1) t = (t * a) % c;
return t;
}
int check(int n)//米勒-拉宾算法
{
srand(time(0));
for(int i = 0; i < 100; ++ i)
{
if(fmod(rand() % (n - 1) + 1, n - 1, n) != 1)//a的值需要变化,所以用到随机函数;a的取值为[1,n-1],因为这样就会保证如果n为素数,则n与a必互质
return 0;
}
return 1;
}
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
if(n < 2)
{
printf("非素数\n");
continue;
}
if(check(n))
printf("素数\n");
else
printf("非素数\n");
}
return 0;
}
分享到:
相关推荐
程序实现了Miller-Rabin算法判断一个数是否是素数
1. 微控制器选择 1. 平台选择 2. 其他开发平台对比 2. 米勒拉宾算法
快速幂模运算,米勒拉宾合数测试,快速素数检测
1. 微控制器选择 1. 平台选择 2. 其他开发平台对比 2. 米勒拉宾算法 1. 前期设计技巧
使用拉宾米勒算法流程写的源码,当时也是借鉴别人的,用来学习。有注释,可以帮你理解这个算法
视频讲解
精典的多模式匹配算法,AC-BM算法的实现代码.在VC6中调试通过.文件中代工程文件.
实现拉宾米勒算法。(测试和工作) 实施扩展欧几里得算法来搜索两个假定素数的 mcd。 生成确定长度的有效密钥对。(测试和工作。推荐的阈值:默认//推荐的密钥对大小:512 或 1024 位) 使用公钥加密消息。 使用密钥...
米勒·拉宾素性检验 使用快速倍增的斐波那契数 生成非斐波纳契数 戊二烯的分段筛分法 快速排序 堆排序 凸包(GrahamScan) 最长递增子序列 合并排序 最接近的点对 基数排序 背包0-1 Nqueens 最长公共子序列 克鲁斯...
用于算法编程竞赛的基本算法和数据结构列表(国际信息学奥林匹克(IOI),ACM国际大学编程竞赛(ICPC),Google Code Jam,Facebook Hacker Cup等)。 过去,此列表对于解决在线法官(例如Sphere在线... 米勒-拉宾素
欧拉公式求长期率的matlab代码...第三组(米勒-拉宾) Eratosthenes筛 分段筛 威尔逊定理-P 素数分解 Pollard的Rho算法 模算术算法 基本和扩展的欧几里得算法 欧拉的Totient函数 模幂 模乘逆 中文余数定理和模逆实现
文档旨在比较费马素性检验、米勒拉宾素性检验,穷举素性检验分别用c++、shell脚本实现后的复杂度检验,进行结果比对,提出并分析问题
米勒-拉宾检验 使用Euclid算法 使用递归 弦 数字 加 减去 乘 划分 功率 号码 到二进制字符串 使用除法和模数 使用右移和模数 使用BigDecimal 使用除法和加倍 是2的幂 使用循环 使用递归 使用对数 使用位 译成英文...
米勒拉宾素性检验 帕斯卡三角形 牛顿法的平方根 快速功率算法 完美的数字 主要原因 素数 线性筛 Pollard 的 Rho 算法 二次残差 辛普森积分规则 快速傅里叶变换 阿姆斯壮数 置换同余随机数生成器 ...
Arithmetic :Elm库,用于整数算术和数论 (在查看文档。) 实现一些有用的功能,包括: 奇偶校验和模块化算法 基本转换 正方形和立方体 ...总理筛和总理检查(米勒-拉宾) 根据BSD3许可证发行。
确定性米勒·拉宾;迪菲;迪菲·赫尔曼;埃尔加马尔密钥生成器;谜机2;希尔密码;混合关键字密码;单字母密码;摩尔斯电码;一键盘密码;Playfair Cipher;波利比乌斯;密码门;拉宾·米勒;铁路围栏密码;腐烂13;RSA 密码;RSA ...
另外采用拉宾-米勒测试法、欧几里得算法、蒙哥马利快速算法等优化算法对于RSA算法的密钥生成、加密等环节进行了速度上的优化,性能得到了明显的提升。本文还将就针对RSA算法的主流攻击手段加以分析,并针对不同的...
拉宾·米勒素数检验 Eratosthenes筛子用于质数 二元搜寻 计算数组中的反转 选择数组中的ith顺序统计量 图形数据结构(有向和无向) 图算法 拓扑排序 最短的啤酒花 DFS BFS 连接的组件 迪克斯特拉的最短道路-O...
Криптологія/ 3курс/ 2сем/ 2020年 实验1 *高级欧几里得算法, * Ferma测试, ... *米勒·拉宾(Miller Rabin)测试, * Mod Pow, *蒙哥马利 实验2 * RC6 实验3 * SHA256
1.数论 素数检验:普通素数判别 线性筛 二次筛法求素数 米勒拉宾素数检验 2.拉格朗日乘子法(求有等式约束条件的极值) 3.裂项(多项式分子分母拆分) 4.扩展欧几里得 (ax+by=c) 5.勾股数 (直角三角形三边长) 6....