基本算法

Miller-Rabin素数测试其实是基于Fermat小定理的一种素数测试方法，其大致思想如下： Fermat小定理：对于素数p和任意正整数a，有ap−1≡1(mod p)a^{p-1} \equiv 1(mod\ p)，反过来，如果满足ap−1≡1(mod p)a^{p-1} \equiv 1(mod\ p)，p就有很大概率是素数 Miller-Rabin：于是，我们不断选取基数b， 计算是否每次都有bn−1≡1(mod p)b^{n - 1} \equiv 1(mod\ p)， 若每次都成立则n是素数，若不成立则为合数 二次探测定理：如果p为奇素数，则x2≡1(mod p)x^2 \equiv 1(mod\ p)的解为x=1x = 1或x=p−1x = p - 1 我们可以利用二次探测定理优化，那么算法就变成了： 尽可能提取因子2，把n-1表示成d∗2nd * 2^n，如果n是一个素数，那么或者ad≡1(mod n)a ^ d \equiv 1(mod\ n)，或者存在某个i使得ad+2r−i≡n−1(mod n)(0≤i≤r−1)a^{d+2^{r - i}} \equiv n-1(mod\ n) (0\le i\le r-1)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;
LL N;
inline LL Mult(LL a, LL b)
{
    LL Ans = 0;
    while (b)
    {
        if (b & 1) (Ans += a) %= N;
        (a += a) %= N;
        b >>= 1;
    }
    return Ans;
}
inline LL Pow(LL a, LL b)
{
    LL Ans = 1;
    while (b)
    {
        if (b & 1) Ans = Mult(Ans, a);
        a = Mult(a, a);
        b >>= 1;
    }
    return Ans;
}
inline int Miller_Rabin()
{
    if (N == 2 || N == 3 || N == 5 || N == 7 || N == 11) return 1;
    if (N == 1 || !(N % 2) || !(N % 3)|| !(N % 5) || !(N % 7) || !(N % 11)) return 0;
    LL u = N - 1, k = 0;
    while (!(u & 1)) ++k, u >>= 1;
    for (int i = 1; i <= 1000; ++i)
    {
        LL x = rand()% (N - 2) + 2;
        x = Pow(x, u);
        LL pre = x;
        for (int j = 0; j < k; ++j)
        {
            x = Mult(x, x);
            if (x == 1 && pre != 1 && pre != (N - 1)) return 0;
            pre = x;
        }
        if (x != 1) return 0;
    }
    return 1;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    scanf("%lld", &N);
    srand(time(0));
    if (Miller_Rabin())
        cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}