b435. 尋找原根

1. Problem
2. Sample Input
3. Sample Output
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

Sample Output

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 提供想法。

一般檢測

#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;
}

加速版本

#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;
}

Morris' Blog