Miller-Rabin素数检测算法笔记

2024-02-19 14:38

本文主要是介绍Miller-Rabin素数检测算法笔记,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

摘自:https://blog.csdn.net/u010646250/article/details/51927085

 

本文内容主要参考《程序员的数学思维修炼》一书中对素数和余数的讲解及这篇博文:
Miller-Rabin素数测试学习笔记
以及这篇文章:
数论部分第一节:素数与素性测试(这篇文章非常好,很清晰的讲解了从素数定义到素数检测算法的过程,比我看到的其他所有资料都好,就是有点长)


先介绍一个概念:互素(或叫互质)

如果a和b两个数的公约数只有1,那么a和b互质,记做(c,m)=1。

根据素数定义,素数与所有小于它的正整数互素。

再介绍几个余数的性质及推广出的几个变换:
(a + b) mod p == (a mod p + b mod p) mod p
(a * b) mod p == ((a mod p) * (b mod p)) mod p
ab mod p == (a mod p)b


要想理解Miller-Rabin,需要先了解一下费马小定理。

Miller-Rabin素数检测算法是基于费马小定理的改进概率算法。

费马小定理

假如p是质数,且(a,p)=1,那么 a^(p-1)≡1(mod p)[或( ap-1 mod p ≡ 1),mod是取模的意思,下同]。即:假如a是整数,p是质数,且a,p互质(即两者只有一个公约数1),那么a的(p-1)次方除以p的余数恒等于1。

(摘自百度百科)

费马小定理是关于素数判定的必要非充分条件,即可以说p是质数且a、p互质的情况下a(p-1)≡1(mod p),而不能说只要满足恒等式且a、p互质,p就一定是素数。由此引出伪素数的概念:

伪素数,又叫做伪质数:它满足费马小定理,但其本身却不是素数。若n能整除2^(n-1)-1 [或(2n-1-1)],并且n是非偶数的合数,那么n就是伪素数。

(摘自百度百科)

事实上,偶伪素数也是存在的,并且已被证明有无穷多个。

在伪素数中,存在一组特殊的数,叫做卡迈克尔数,定义为:

对于合数n,如果对于所有正整数b,b和n互素,都有同余式b^(n-1)≡ 1 (mod n) [或(bn-1 mod n ≡ 1)]成立,则合数n为Carmichael数。

(摘自百度百科)

可见,卡迈克尔数一定是合数,且满足费马小定理。卡迈克尔数也被证明有无穷多个,而前一亿个数中,只有255个卡迈克尔数。

庆幸的是,虽然费马小定理的逆定理不完全成立,但在大多数情况下还是有效的。

Fermat素性测试

基于费马小定理 ap-1 mod p≡1公式,(随机地)选取若干个小于p的正整数为a,若所有的a都满足p-1 mod p≡1,则基本认为p是素数。

Fermat素性测试实际上就是对费马小定理的应用。

统计表明,在前10亿个自然数中共有50847534个素数,而满足2^(n-1) mod n = 1的合数n有5597个,这些合数都是以2为底的伪素数。其中一些合数可能在a=2时通过了测试,却不能通过a=3时的测试。能同时通过a=2和a=3的测试的合数叫做以2和3为底的伪素数,前10亿中只有1272个。所以,Fermat素性测试需要做相互独立的若干轮随机测试来降低出错的可能性。

然而,坑爹的是,即使取遍1到n-1的所有整数进行素性测试,仍然会存在一些伪素数没有被查出来,这些数被称为卡迈克尔数(上文有介绍),前10亿中有600多个。

Miller-Rabin素数测试

Miller-Rabin素数测试基于下面的新定理:

如果p是素数,x是小于p的正整数,且x2 mod p = 1,那么要么x=1,要么x=p-1。这是显然的,因为x2 mod p = 1相当于p能整除x2-1,也即p能整除(x+1)(x-1)。由于p是素数,那么只可能是x-1能被p整除(此时x=1)或x+1能被p整除(此时x=p-1)。(ps:素数p只能整除0和它自己)

(摘自数论部分第一节:素数与素性测试)
通过上面这个定理来加强费马小定理,可以得到这个公式:
ad*2r mod p =1
根据上面的定理和公式,在进行Fermat测试时,还需测试d*2r-1时ad*2r mod p是否等于1或者p-1,如果通过则测试d*2r-2时是否成立,直到r=0或者ad*2r-s mod p = p-1,其中0≤s≤r-1。

要测试N是否为素数,首先将N-1分解为 2sd。在每次测试开始时,先随机选一个介于[1,N-1]的整数a,之后如果对所有的r∈[0,s-1],若ad mod N≠1且a2rd≠-1则N是合数。否则,N有3/4的概率为素数。

(摘自维基百科)

上面用新定理加强费马小定理的原理我本人并不是很理解,所以这里用一种自己想到的方法来解释(可能是错的,不要介意 ʅ(‾◡◝))。

ap-1 mod p=1 –>
ad*2r mod p=1 –>
(ad*2r-1)2 mod p=1 –>
(ad*2r-1 mod p)*(ad*2r-1 mod p)=1
所以(ad*2r-1 mod p)的结果只能是±1,其中-1等价于p-1。

如果最上面的式子成立,那么后面的式子都应该成立,并且可以重复其中的过程直到r=1,或者等式右边是p-1。如果右边是p-1,那么式子就不能继续分解下去,过程到此为止。

有人将上面利用加强费马小定理测试素性的过程叫做Miller测试。

通过上面的素性测试可以有效筛掉大部分伪素数。比如,基于原本的费马小定理,341是个最小的底为2的伪素数,而用加强费马小定理,最小的底为2的伪素数是2047,最小的底为2和3的伪素数则是1 373 653,可见效果是非常显著的。

完整的Miller-Rabin素数检测过程就是:进行相互独立的k轮测试,每轮在小于待测素数p的正整数中随机选取a的值,利用加强费马小定理进行Miller测试,通过所有测试的p就可以认为是素数,p被误判的概率是4-k。

有一些非常实用的现成结论可以在进行素数测试时降低算法运行时间:如果被测数小于4 759 123 141(47亿),那么只需要测试三个底数2, 7和61就足够了;如果每次都用前7个素数(2, 3, 5, 7, 11, 13和17)进行测试,所有不超过341 550 071 728 320(3百万亿)的数都是正确的;如果选用2, 3, 7, 61和24251作为底数,那么10^16内唯一的强伪素数为46 856 248 255 981(4.6*1013)。

下面是Miller-Rabin素数检测的流程图:

开始将p-1表示成d*2^r 选择底数a,素数测试论述s计算 a^(d*2^r) mod p结果等于1?r>0?s>1?r=r-1,s=s-1是素数结束结果等于p-1?不是素数yesnoyesnoyesnoyesno

变量s是控制测试轮数的,实时上没有必要将0~s之间所有的数都测一遍,就像上面所说,选择几个特定的数就足以覆盖大部分情况。

 

这篇关于Miller-Rabin素数检测算法笔记的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/724981

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

烟火目标检测数据集 7800张 烟火检测 带标注 voc yolo

一个包含7800张带标注图像的数据集,专门用于烟火目标检测,是一个非常有价值的资源,尤其对于那些致力于公共安全、事件管理和烟花表演监控等领域的人士而言。下面是对此数据集的一个详细介绍: 数据集名称:烟火目标检测数据集 数据集规模: 图片数量:7800张类别:主要包含烟火类目标,可能还包括其他相关类别,如烟火发射装置、背景等。格式:图像文件通常为JPEG或PNG格式;标注文件可能为X

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识