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^{\phi(m)} \equiv 1 \mod m \\ g^{\gamma} \not\equiv 1 \mod m \text{ , for } 1 \le \gamma < \phi(m)$$

意即在模 $m$ 下,循環節 $ord_m(g) = \phi(m)$,若 $m$ 是質數,則 $\phi(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^{\phi(p)} \equiv 1 \mod p$,那麼可以堆導得到若 $a^x \equiv 1 \mod p$,則滿足 $x | \phi(p)$,否則與歐拉矛盾,藉此可以作為一個篩選的檢查手法,對於所有 $phi(p)$ 的因數都進行檢查,最後我們可以得到 一般檢測 的作法。

為了加速驗證,由於 $x | \phi(p)$,若最小的 $x$ 存在 $a^x \equiv 1 \mod p$,那麼 $kx$ 也會符合等式,因此只需要檢查 $x = (p-1)/\text{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;
}