hiho一下 第九十二周 数论一·Miller-Rabin质数测试

HiHo
HiHo一下的合集参见这里，不断更新

输入

第1行：1个正整数t，表示数字的个数，10≤t≤50

第2..t+1行：每行1个正整数，第i+1行表示正整数a[i]，2≤a[i]≤10^18

输出

第1..t行：每行1个字符串，若a[i]为质数，第i行输出"Yes"，否则输出"No"

样例

//样例输入
3
3
7
9
//样例输出
Yes
Yes
No

数论拾遗

素数一直是数论的重要一环，这里给出有关素数的四个有趣的性质的证明，来自Matrix67的blog。

素数的个数无限多（不存在最大素数）

证： 反证法。加上存在最大的素数P，令 $$Q=2*3*5*...*P+1$$ 所有到P的素数相乘再加一。
那么这个数显然是素数，因为所有素数除它都余1。得证。

存在任意长的一段连续数，其中所有数都是合数

证：
首先当$0<a\le n$时,$n!+a$能被$a$整除。
那么对于长度为$n-1$的数列$(n!+2),(n!+3)\sim(n!+n)$他们都是合数。
而$n\in[2,+\infty)$,得证。

所有大于2的素数都能唯一的表示为两个平方数之差

证：大于2的素数都是奇数，所以设这个数为$2n+1$。
$$(n+1)^2=n^2+2n+1$$ $$2n+1 = (n+1)^2-n^2$$ 这就证明了该素数能表示为两个平方数之差，下面证明唯一性。
$$设：素数p = a^2-b^2$$ $$p=(a+b)(a-b)$$
因为p为素数，所以p的因子只有1和它本身，所以只可能$a+b=p$,$a-b=1$这就是唯一解。

当n为大于2的整数，$2^n+1和2^n-1$两个数，若其中一个为素数，那么另一个一定是合数

证：
因为$2^n$肯定不能被3整除，那么就剩下两种情况。
1. $2^n$除3余1，那$2^n-1$能被3整除。
2. $2^n$除3余2，那$2^n+1$能被3整除。
得证。

然后就是本题中会用到的算法的原理————费马小定理（Fermat's Little Theorem）

费马小定理

p为素数，a是小于p的正整数，那么有 $$a^{p-1}\ mod\ p \equiv 1$$

这个定理的逆命题并不正确，即若$a^{p-1}\ mod\ p \equiv 1，a<p$,p不一定为素数（但是若不满足这个调节一定不是素数）。但是这时候p为素数的概率非常大，也就有了Fermat测试，取a=2，计算$2^{p-1}\ mod\ p$,若等于1，说明有可能为素数，然后可以试试不同的a，也可以制作一张伪素数表，查找p是否是伪素数。

思路

但是如果不用伪素数表，那么在前10亿个自然数中使用单次Fermat测试，出错的概率是0.00011，有点高了。所以人们想到改进这个算法。
Miller和Rabin在Fermat测试上，建立了Miller-Rabin质数测试算法。

与Fermat测试相比，增加了一个二次探测定理：

如果p是奇素数，则 x^2 ≡ 1(mod p)的解为 x ≡ 1 或 x ≡ p - 1(mod p)

如果a^(n-1) ≡ 1 (mod n)成立，Miller-Rabin算法不是立即找另一个a进行测试，而是看n-1是不是偶数。如果n-1是偶数，另u=(n-1)/2，并检查是否满足二次探测定理即a^u ≡ 1 或 a^u ≡ n - 1(mod n)。

代码