Miller-Rabin素數測試

Miller-Rabin素數測試

給出一個小于1e18的數，問它是否為質數？不超過50組詢問。hihocoder

我是真的菜，為了不誤導他人，本篇僅供個人使用。

首先，一個1e18的數，樸素\(O(\sqrt{n})\)素數判定肯定爆炸。怎么辦呢？

我們知道，對于素數p，只要a不是p的倍數，一定有\(a^{p-1}=1\mod p\)。那么，我們是不是可以選出某些a，對于要判定的數p，看看他是否滿足以a為底的費馬小定理，以此來判定質數呢？答案是基本可以。

但是很不巧，有一類合數，以任何小于它們的質數為底進行判定，結果都是正確的。它們叫做偽素數。怎么排除偽素數的情況呢？有個叫做二次探測定理的東西：若\(x^2=1\mod p\)，那么\(或x=1或-1\mod p\)。

假設\(a^{x-1}=1\mod p\)成立。如果x-1為奇數，就不再判定下去。否則，根據二次探測定理，還可以繼續去判定\(或a^{\frac{x-1}{2}}=1或-1\mod p\)是否成立。如果它不等于1或-1，就返回false。如果它等于-1，就返回true。如果它等于1，就繼續判定下去。反正，只要x-1為偶數，并且\(a^{x-1}=1\mod p\)，就可以一直判定。這樣就可以把那些偽素數排除掉了。這就叫做miller-rabin素數測試。據說選前7個質數作為a，在1e18內也只有兩三個會被miller-rabin判定成素數的合數。

#include <cstdio>
using namespace std;typedef long long LL;
const LL m=7, a[m]={2, 3, 5, 7, 11, 13, 17};
LL n, p;LL fmul(LL a, LL b, LL p){  //將b分解為二進制，返回a*b%pLL ans=0;for (; b; b>>=1, a+=a, a%=p)if (b&1) ans+=a, ans%=p;return ans;
}LL fpow(LL a, LL x, LL p){LL ans=1, base=a;for (; x; x>>=1, base=fmul(base, base, p))if (x&1) ans=fmul(ans, base, p);return ans;
}bool MR(LL a, LL x, LL p){  //判斷是否a^x=1或p-1 (mod p)，且mr下去也成立LL t=fpow(a, x, p);if (t!=1&&t!=p-1) return false;if (t==1&&x&1||t==p-1) return true;return MR(a, x>>1, p);
}bool isprime(LL p){if (p&1==0) return false;for (LL i=0; i<m; ++i){if (p==a[i]) return true;  //互質時費馬小定理才成立if (fpow(a[i], p-1, p)!=1) return false;if (!MR(a[i], (p-1)>>1, p)) return false;}return true;
}int main(){scanf("%lld", &n);while (n--){scanf("%lld", &p);puts(isprime(p)?"Yes":"No");}return 0;
}