MENU

LibreOJ#143/洛谷P3383/AtCoder Regular Contest 017-A/洛谷P1835/COGS2489 质数判定/【模板】线性筛素数/素数、コンテスト、素数/素数密度

LibreOJ#143

洛谷P3383

AtCoder Regular Contest 017-A

洛谷P1835

COGS2489

费马小定理:若$(a,p)=1$,则$a^{p-1} \equiv 1 \pmod p$。

二次探测定理:若$p$为素数,$a^2 \equiv 1 \pmod p$,则$a \equiv 1 \pmod p$。

我们下面来演示一下上面的定理如何应用在Fermat素性测试上。前面说过$341$可以通过以$2$为底的Fermat测试,因为$2^{340} \bmod 341=1$。如果$341$真是素数的话,那么$2^{170} \bmod 341$只可能是$1$或$340$;当算得$2^{170} \bmod 341$确实等于$1$时,我们可以继续查看$2^{85}$除以$341$的结果。我们发现,$2^{85} \bmod 341=32$,这一结果摘掉了$341$头上的素数皇冠,面具后面真实的嘴脸显现了出来,想假扮素数和我的素MM交往的企图暴露了出来。
这就是Miller-Rabin素性测试的方法。不断地提取指数$n-1$中的因子$2$,把$n-1$表示成$d \times 2^r$(其中$d$是一个奇数)。那么我们需要计算的东西就变成了$a$的$d \times 2^r$次方除以$n$的余数。于是,$a^{d \times 2^{r-1}}$要么等于$1$,要么等于$n-1$。如果$a^{d \times 2^{r-1}}$等于$1$,定理继续适用于$a^{d \times 2^{r-2}}$,这样不断开方开下去,直到对于某个$i$满足$a^{d \times 2^i} \bmod n = n-1$或者最后指数中的$2$用完了得到的$a^d \bmod n=1$或$n-1$。这样,Fermat小定理加强为如下形式:
尽可能提取因子$2$,把$n-1$表示成$d \times 2^r$,如果$n$是一个素数,那么或者$a^d \bmod n=1$,或者存在某个$i$使得$a^{d \times 2^i} \bmod n=n-1 (0 \le i<r )$ (注意$i$可以等于$0$,这就把$a^d \bmod n=n-1$的情况统一到后面去了)
Miller-Rabin素性测试同样是不确定算法,我们把可以通过以$a$为底的Miller-Rabin测试的合数称作以$a$为底的强伪素数(strong pseudoprime)。第一个以$2$为底的强伪素数为$2047$。第一个以$2$和$3$为底的强伪素数则大到$1373653$。
Miller-Rabin算法的代码也非常简单:计算$d$和$r$的值(可以用位运算加速),然后二分计算$a^d \bmod n$的值,最后把它平方$r$次。

数论部分第一节:素数与素性测试

水博文真开心

#include<cstdio>
long long x;
const int arr[] = { 3, 5, 7, 11, 13, 17, 19, 23 };
inline long long pow(long long a, long long b, long long p) {
    long long ret = 1;
    for(; b; b >>= 1, a = (__int128) a * a % p)if(b & 1) ret = (__int128) ret * a % p;
    return ret;
}
bool judge() {
    if(x == 1)return 0;
    long long t = x - 1;
    int cnt = 0;
    while(!(t & 1))++cnt, t >>= 1;
    for(int cur : arr) {
        if(x == cur)return 1;
        long long a = pow(cur, t, x), next = a;
        for(long long j = 1; j <= cnt; ++j) {
            next = (__int128) a * a % x;
            if(next == 1 && a != 1 && a != x - 1)return 0;
            a = next;
        }
        if(a != 1)return 0;
    }
    return 1;
}
int main() { while(scanf("%lld", &x) == 1)puts(judge() ? "Y" : "N"); }