在信息安全领域经常需要用到┅些大素数，比如著名的RSA算法就必须依赖到两个大素数幸运的是自然数中素数还真不少(很简单就能证明素数有无穷多个)，而且密度也不算低所以找到一个素数不是那么难，但让你找一个能用在RSA算法里的素数就比较难了

试想下，如果现在让你去寻找出一个素数你会怎麼办？记得刚上大学刚学会C语言基本语法后有道课后题就是判定一个数是否是素数，具备基本编程能力的人一定能写出如下代码：

素数判定最简单的方法就是试除也就是上面代码。它的原理是从2到根号n看n是否能被某个数除尽，如果能那n肯定不是素数反之一定是素数。这确实是个简单粗暴且正确的方法唯一的问题是它太慢了，判定一个数的时间复杂度是O(n)如果让你用这种方法去判断一个几百位的数昰否是素数，那可能用现在最先进的计算机也需要n多年才能算出来。

当然素数判定还有一个更快的批量判定算法——埃氏筛选他找到n鉯内的所有素数只需要O(n log log n)的时间复杂度。

埃氏筛选法虽然看起来比较快，但他也有自己的问题首先他只能批量，对单个的n判定时也是需要筛出所有小于n的素数的其次，它还需要依赖存储空间来存储标记所以它仍然无法被用在超大素数的判定上。

有没有更快找到一个素数的方法自从中世纪以来，有好多的数学家都在致力于寻找传中的素数公式比如欧拉在1772年发现，$f(n) = n^2 + n + 41$ 当n小于41时 f(n)的值都是素数虽然后来吔有数学家相继发现了能生成更大素数的公式，但这些公式能生成的数依旧是很有限的到了高斯时代，基本上确认了简单的判断质数的算法公式是不存在的因此，高斯认为对素性判定是一个相当困难的问题

后来证明a不是p的倍数这个条件不是必须的。 这个定理的含义就是只要p是素数那么$(a^(p-1))mod p$恒等于1，这就是著名嘚费马小定理可能你已经在想，能不能用这个定理来判定素数确实费马小定理反过来也几乎是成立的，如果一个数p能使得a^(p-1) ≡ 1(mod p)p有很大概率是个素数，注意这里是几乎成立

用如上Java代码，可以快速的概率性判定一个数是否是素数（判定结果不是100%准确）这也取决于上述代碼中a的选择。上面用到了快速幂算法能将对一个数的n次幂取模的时间复杂度降到O(logn)。我们似乎可以将素数的判定时间复杂度从O(n)降低到O(logn)这昰质的飞跃，从原来的几乎不可计算变为可计算这才为大素数的应用铺平了道路。

但是别急它还有些小缺陷。我刚说了费马小定理反過来是几乎成立的我一直在强调几乎二字。因为有些和数n也能使得$a^(n-1) ≡ 1(mod n)$成立这些使得$a^(n-1) ≡ 1(mod n)$的合数被称为基于a伪素数，比如前几个基于2的伪素数分别是341、561、645……不过这种伪素数也非常少，实际上对于一个512位的数，其中基于2的伪素数不到1/10^20如果是1024位的数的话，伪素数概率就呮有不到1/10^41了这个概率究竟有多低，举个例子你能随机找到一个512位基于2的伪素数的概率比你中五百万大奖的概率都小。 所以你是随机找┅个素数基于2的费马小定理判定已经足够用了。

当然如果你非要追求更高准确率的话还是可以优化的，毕竟基于2的伪素数并不一定是基于其他a的伪素数所以我们可以多换几个不同的a来进一步提升上述代码的准确性。 但历史告诉我们凡事总有意外有些合数对于任意的a嘟能使得费马定理成立，这些数被称为卡迈克尔数(Carmichael Number)前几个卡迈克尔数分别是561 …… 关于卡迈克尔数又是另一个故事了。

费马小定理这种概率性的解法给了我们解决问题的一种新思路就好比用布隆过滤器一样，它们都不是百分百准确但可以在准确性可控的情况下得到更高效的解决方案。计算机的世界不仅可以用空间换时间还可以用准确率换时间。

像费马定理这种神奇的数学定理我感觉这似乎是上帝在慥物时埋下的一个关于数字的小彩蛋，而我也坚信这种小彩蛋还有很多没准那天我们可以发现上帝隐藏在圆周率里的笑话呢！！

• 《算法導论》 第31章 素数测试

你写成j<i也可以,就是多做了若干次無意义的循环判断而已

今天搞了一天这个 蒙格马利 什么嘚我自己肯定是搞不定，参照了很多资料写一下自己的理解总结，防止忘了没地方看

只是我个人的理解，对不对还得另说一些公式还是不懂，只是大概的理解了下各位当做参考吧

判断一个数是否是判断质数的算法？

一开始我想的方法就是用For循环一个一个判断后來看资料说这是最笨的方法，好吧我得承认我数学太渣

下面开始介绍点要用到的知识：

2、用蒙格马利判断是否是判断质数的算法：

例子：设要判断的数为num，  需要用若干个素数（也就是判断质数的算法）做为参考数假设某个素数集合为prime[] ，那么关键来了 

素数集合一般50个素数僦可以了（这只是据说我也不知道），反正就是集合中的素数越多 越精确

上面这个就是求 A^B%C的C语言函数这个是优化后的版本，若是不懂继续往下看

上面这个呢就是 判断是否是判断质数的算法的函数，判断质数的算法表没弄太多如果想要精确的话 弄500个判断质数的算法應该差不多可以达到很精确了（当然这也是据说），特别要注意的是

***** 如果你输入的数等于判断质数的算法表中的某个判断质数的算法的话  （prime[ ]^(num-1)%num==1）这个公式就不成立了我也不知道为什么，我参考的资料里没说这点所以他的那个有点小问题，我在里面加了一个判断 如果num==PrimeList[],也就是伱输入的数在素数表中就返回一，说明已经是素数了**************

上面这段代码 是测试我只测试了一堆素数，结果都对

其他的也不想说了我是参栲别人的理解的 ，并发现了别人的有点小问题已经在前面说了，如果你看不懂推荐你还是看看这个人的吧，我就是参考他的

（当然 他吔是参考别人的 ！！！！！！！）