miller_rabin素性测试

给出一个非常大的数，判断它是不是素数
对于较小的数，可以枚举 $[1,\sqrt{n}]$ 内每一个数试除，若能整除则非素数，这么做的复杂度为 $O(\sqrt{n})$
对于较大的整数，如 $10^{16}$ 级别的数，不够用了
所以去学了一下miller_rabin测试法
miller_rabin测试法是一个随机算法，虽然不能保证完全正确，但是判断64位整数范围内的数够了(大概

费马小定理

若 $p$ 是素数且 $\gcd(a,p)==1$ ，则 $a^{p-1}\equiv 1\mod p$
我们可以随机的枚举 $[1,n-1]$ 范围内的数，若不符合上述定理，则 $n$ 显然是合数
但是这个定理只是必要条件，并不是充分条件
存在一类叫做卡迈克尔数的数，也满足上述条件，但是他们是合数，比如 $561$

二次探测定理

若 $p$ 是奇素数，则 $x^2\equiv1\mod p$ 的解要么是 $x=1\mod p$ ,要么是 $x=p-1\mod p$
证明

因为 $x^2\equiv1\mod p$ ，所以 $x^2-1\equiv 0 \mod p$
所以 $(x+1)(x-1)\equiv 0 \mod p$
所以 $x+1\equiv 0 \mod p->x\equiv p-1\mod p$
或者 $x-1\equiv 0 \mod p->x\equiv 1\mod p$

做法

结合上述两个定理同时来判断，就可以大大提高测试的准确性

对于一个整数 $x$ ，如果是偶数直接返回 $false$ 即可
如果是奇数，随机一个 $[1,n-1]$ 的整数 $c$ ,令 $k=x-1$ ,则 $k=u\times 2^d$
如果 $c^{k}\equiv 1\mod n$ 那么继续判断 $c^{\frac{k}{2}}\equiv 1 \mod n$ 依此类推，直到 $c^k=n-1\mod n$ 或者 $c^k!=1\mod n$
因为如果 $n$ 是一个素数，且 $c^k\equiv 1\mod n$ 那么 $\sqrt{c^k}=c^{\frac{k}{2}}\equiv 1\mod n$ 或者 $\sqrt{c^k}=c^{\frac{k}{2}}\equiv n-1\mod n$ ，对于第一个情况可以继续递归，对于第二个情况可以直接返回结果

数学-miller_rabin测试

miller_rabin素性测试

费马小定理

二次探测定理

做法