OceanEye's Blog

很多人即使只见过一面,已经算见过了最后一面。

@OceanEye7年前

08/7
16:03
OI

Miller_Rabin 素数判定

0x00

Miller_Rabin 素数判定
为什么要写这个……因为我把它忘掉了
于是写篇文章复习复习……

0x01

基础知识:

费马小定理

\(a^{n-1} \equiv 1\pmod n\)

伪素数

如果n是一个正整数,如果存在和n互素的正整数a满足 \( a^{n-1} \equiv 1\pmod n\),我们说n是基于a的伪素数。如果一个数是伪素数,那么它是素数的可能性很大

Miller-Rabin测试

不断选取不超过\(n-1\)的基\(b\)(\(s\)次),计算是否每次都有\( b^{n-1} \equiv 1\pmod n\),若每次都成立则n是素数,否则为合数。

快速幂

这是基础知识……

快速乘

快速乘是在模意义下的乘法
具体来说就是a*b%c超出限制的时候用的 , 用了位运算的技巧
代码如下

0x02

上面有了伪素数的定义……那么我们可以用一些朴素的方法来验证素数
比如……我们随机几个数然后跑跑

大概每次筛正确的概率是 \( frac{3}{4} \)

0x03

然后讲一个不是那么的平凡的优化
因为 \( a^{n-1} \equiv 1\pmod n\)
所以 \( a^{\sqrt{n-1}^{2}} \equiv 1 \pmod n\) 或者 \(a^{\sqrt{n-1}^{2}} \equiv n-1\pmod n\)
如果使用的话可以提高该算法的效率

参考以下的代码

Miller_Rabin 素数判定