Processing math: 100%
解題區/解題區 - Zerojudge

b435. 尋找原根

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. 一般檢測
    2. 4.2. 加速版本

Problem

給定一個模數 m，找到其 primitive root g。

primitive root g 滿足

gϕ(m)≡1modmgγ≢1modm , for 1≤γ<ϕ(m)

意即在模 m 下，循環節 ordm(g)=ϕ(m)，若 m 是質數，則 ϕ(m)=m−1，也就是說循環節長度是 m−1，更可怕的是組成一個 [1,m−1] 的數字排列。

現在假定 m 是質數，請求出一個最小的 primitive root g。

Sample Input

1
2
3
4
2
3
5
7

Sample Output

1
2
3
4
1
2
2
3

Solution

primitive root 在密碼學中，用在 Diffie-Hellman 的選定中的穩定度，倘若基底是一個 primitive root 將會提升破解的難度，因為對應情況大幅增加 (值域比較廣，因為不循環)。

由於歐拉定理，可以得知 aϕ(p)≡1modp，那麼可以堆導得到若 ax≡1modp，則滿足 x|ϕ(p)，否則與歐拉矛盾，藉此可以作為一個篩選的檢查手法，對於所有 phi(p) 的因數都進行檢查，最後我們可以得到 一般檢測 的作法。

為了加速驗證，由於 x|ϕ(p)，若最小的 x 存在 ax≡1modp，那麼 kx 也會符合等式，因此只需要檢查 x=(p−1)/prime-factor 的情況，如此一來速度就快上非常多。最後得到 加速版本 ，此做法由 liouzhou_101 提供想法。

一般檢測

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
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
#define MAXL (50000>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
int mark[MAXL];
int P[5500], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 45825;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
vector< pair<int, int> > factor(int n) {
    vector< pair<int, int> > R;
    
    for(int i = 0, j; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {
            for(j = 0; n%P[i] == 0; n /= P[i], j++);
            R.push_back(make_pair(P[i], j));
        }
    }
    if(n != 1)	R.push_back(make_pair(n, 1));
    return R;
}
void gen_factor(int idx, int x, vector< pair<int, int> > &f, vector<int> &g) {
    if (idx == f.size()) {
        g.push_back(x);
        return ;
    }
    for (int i = 0, a = 1; i <= f[idx].second; i++, a *= f[idx].first) 
        gen_factor(idx+1, x*a, f, g);
}
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y&1) 
            ret = (ret * x)%mod;
        y >>= 1, x = (x * x)%mod;
    }
    return ret % mod;
}
int primitive_root(int p) {
    if (p == 2)	return 1;
    vector< pair<int, int> > f = factor(p-1);
    vector<int> g;
    gen_factor(0, 1, f, g);
    g.erase(g.begin()), g.pop_back();	// remove 1, p-1
    random_shuffle(g.begin(), g.end());
    for (int i = 2; i <= p; i++) {
        int ok = 1;
        for (auto &x: g) {
            if (mpow(i, x, p) == 1) {
                ok = 0;
                break;
            }
        }
        if (ok)	return i;
    }
    return -1;
}
int main() {
    sieve();
    int p;
    while (scanf("%d", &p) == 1) 
        printf("%d\n", primitive_root(p));
    return 0;
}

加速版本

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
#include <bits/stdc++.h>
using namespace std;
#define MAXL (50000>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
int mark[MAXL];
int P[5500], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 45825;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
vector< pair<int, int> > factor(int n) {
    vector< pair<int, int> > R;
    
    for(int i = 0, j; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {
            for(j = 0; n%P[i] == 0; n /= P[i], j++);
            R.push_back(make_pair(P[i], j));
        }
    }
    if(n != 1)	R.push_back(make_pair(n, 1));
    return R;
}
long long mpow(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y&1) 
            ret = (ret * x)%mod;
        y >>= 1, x = (x * x)%mod;
    }
    return ret % mod;
}
int primitive_root(int p) {
    if (p == 2)	return 1;
    vector< pair<int, int> > f = factor(p-1);
    for (int i = 2; i <= p; i++) {
        int ok = 1;
        for (auto &x: f) {
            if (mpow(i, (p-1)/x.first, p) == 1) {
                ok = 0;
                break;
            }
        }
        if (ok)	return i;
    }
    return -1;
}
int main() {
    sieve();
    int p;
    while (scanf("%d", &p) == 1) 
        printf("%d\n", primitive_root(p));
    return 0;
}