原始问题

给定任意一个正整数m(>1)m(>1)，编程解决以下问题：

  1. 判断是否存在模 mm 的原根
  2. 如果存在
    • 给出模 mm 的所有原根
    • 基于原根生成正整数 mm 的简化剩余系

基础知识

指数和原根

设 m>1m > 1 是整数，aa 是与 mm 互素的正整数，根据欧拉定理，有 aφ(m)≡1(mod m)a^{\varphi(m)}\equiv1(mod\ m)

其中φ(m)\varphi(m)（Eular函数）表示从1到 m−1m-1 中与 mm 互素的数的个数

而使得 ae≡1(mod m)a^e \equiv 1(mod \ m) 成立的最小正整数 ee ，叫做 a对模m的指数

如果这个时候，恰好有 e=φ(m)e = \varphi(m)，那么称 aa 为模m的原根

谁要看定义啊喂

咳咳，其实简单来说就是

当 aφ(m)≡1(mod m)a^{\varphi(m)}\equiv1(mod\ m) ，且没有更小的数 ee 能使得 ae≡1(mod m)a^e \equiv 1(mod\ m)时，aa 就是模 mm 原根

模m原根的存在条件

定理：模 mm 原根存在的充要条件是 m=2,4,pα,2pα,其中 p 是奇素数.m=2,4,p^\alpha,2p^\alpha,其中\ p\ 是奇素数.

你问我为什么？你管他为什么，记住就完了

埃氏筛法

其实就是给定整数 nn，求 1∼n1\sim n 的所有质数（素数）。

算法的基本思想 ：从2开始，将每个质数的倍数都标记成合数，以达到筛选素数的目的。

优点：时间复杂度比“ 对每个数 i 从2到ii\ 从2到\sqrt i 都判断一遍是否能除尽 ”的方法低，具体为 O(nln⁡ln⁡n)O(n\ln\ln n)

一个原根 →\rightarrow简化剩余系 & 所有原根（？）

如果我们现在找到了一个模 mm 的原根 gg，那么 g0,g1,⋯ ,gφ(m)−1g^0,g^1,\cdots,g^{\varphi(m)-1} 遍历 mm 的一个简化剩余系

那么由一个原根是否可以推出所有原根呢？仿佛有这么一条结论：

假设正整数 dd 遍历 p−1p - 1 的一个简化剩余系（设为 r0,r1,⋯ ,rφ(p−1)−1r_0,r_1,\cdots,r_{\varphi(p-1)-1}）

那么 gd(mod p)g^d(mod\ p) （gr0,⋯ ,grφ(p)−1g^{r0},\cdots,g^{r_{\varphi(p)-1}}）遍历模 pp 的所有原根

但是，需要注意的是，这条结论针对的是模 p (奇素数)p\ (奇素数) 原根的情况，并不是对于任意 mm 都成立

问题解决

判断是否存在模m原根

根据基础知识-模m原根存在的条件中的定理可知，对于大于1的正整数 mm，要判断是否存在模 mm 的原根，只需要判断 m=2,4,pα,2pα 是否成立,其中 p 是奇素数m=2,4,p^\alpha,2p^\alpha\ 是否成立,其中\ p\ 是奇素数 是否成立即可。

第一步，求出从1~m所有的奇素数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef long long LL

// 埃氏算法求出从1到m的所有素数
// 函数返回后，prime[i] = 0表示i为合数，prime[i] = 1表示i为素数
void Eratosthenes(LL m, vector<int> &prime) {
    prime.resize(m + 1);			// 初始化prime容器的大小
    for(LL i = 2; i <= m; i ++) {
        prime[i] = 1;				// 首先全部标记为素数
    }
    prime[0] = 0, prime[1] = 0;		// 0和1既不是素数也不是合数
    for(LL i = 2; i <= m; i ++) {
        if(prime[i] == 0) continue;	// 如果之前被判断出是合数则跳过
        LL tmp = i;
        while((tmp += i) <= m) {	// i为素数，m以内i的倍数全都标记为合数
            prime[tmp] = 0;
        }
    }
}
第二步，暴力判断 mm 是否为2,4,pa 或 2pa2,4,p^a\ 或\ 2p^a
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 判断m是否为2,4,p^a或2p^a,即是否有原根
bool judge(LL m, vector<int> prime) {
    if(m == 2 || m == 4) return true;
    for(LL p = 3; p <= m; p ++) {
        if(prime[p] == 0) continue;	//对于每个<=m的素数p
        LL i = 1;
        while(true) {
            LL target = pow(p, i);	
            if(target > m) break;	//p^i超过m则找下一个p
            if(target == m || target * 2 == m) 
                return true;		//找到了m=p^a或2p^a的情况
            i ++;
        }
    }
    return false;					//没找到，返回false
}

找出所有模m原根

  • 如果 mm 为奇素数，按照基础知识-一个原根→简化剩余系&所有原根节中所述，可以先求出 m−1m - 1 的简化剩余系，再由简化剩余系生成模 mm的所有原根
  • 如果 mm 不为奇素数，那么只能对于所有小于 mm 且与 mm 互素的正整数进行暴力算法判断，即判断 e=φ(m)e=\varphi(m) 是否为使得 ae≡1(mod m)a^e\equiv1(mod\ m) 成立的最小正整数
第一步 求 φ(m)\varphi(m)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 欧拉函数，求出φ(m)的值
// n = p1^a1 ... ps^as
// φ(n) = φ(p1^a1)...φ(ps^as)
// φ(p^a) = (p-1)*p^(a-1)
LL Eular(LL num, vector<int> prime) {
    if(prime[num] == 1) return (num - 1);	// 如果是素数，直接返回n-1
    LL res = 1;
    for(LL i = 2; i <= num; i ++) {
        if(prime[i] == 0) continue;		    // 找素因数
        LL a_i = 0;
        while(num % i == 0) {			   	// 找到一个pi
            a_i ++;							// 求出pi对应的ai
            num /= i;
        }
        if(a_i != 0) 						// φ(p^a) = (p-1)*p^(a-1)
            res *= (i - 1)*pow(i, a_i - 1);	// φ(p^a) = (p-1)*p^(a-1)	
    }
    return res;
}

第二步 判断一个数是否与m互素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 判断两个数是否互素
bool is_coprime(LL a, LL b, vector<int> prime) {
    if(a == b) 
        return false;				// 如果相等肯定不互素
    if(a == 1 || b == 1) 
        return true;				// 1与任何数互素
    if(a % b == 0 || b % a == 0) 
        return false;				// 如果可以整除另外一个数，不互素
    if(prime[a] == 1 || prime[b] == 1) 
        return true;				// 不能整除时，有一个是素数则互素
    // 剩下就是两个数都是合数的情况
    LL ceiling = min(a, b);			// 取较小的那个数
    for(LL i = 2; i <= ceiling; i ++) {
        if(prime[i] == 0) continue;
        if(a % i == 0 && b % i == 0) 
            return false;			// 如果有公共素因子，不互素
    }
    return true;					// 其他情况，互素
}

第三步 计算 ae(mod m)a^e(mod\ m)
1
2
3
4
5
6
7
8
9
10
11
12
// 模平方重复法（快速幂），求a^e(modm)
LL quick_pow(LL a, LL e, LL m) {
    LL answer = 1, base = a % m;
    while (e != 0)
    {
        if (e & 1)
            answer = (answer * base) % m;
        base = (base * base) % m;
        e >>= 1;
    }
    return answer;
}
第四步 求解所有原根
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
// 对于非奇素数m，用暴力的方法求出所有原根
void find_roots(LL m, vector<int> prime, vector<LL> &roots, LL phi_m) {
    for(LL a = 1; a < m; a ++) {
        if(is_coprime(a, m, prime)) {			// 先判断a、m是否互素
            bool flag = true;
            for(LL e = 1; e < phi_m; e ++) {	// 寻找有没有小于φ(m)的e
                if(quick_pow(a, e, m) == 1) {
                    flag = false;				// 找到了，则a不是原根
                    break;
                }
            }
            if(!flag) continue;
            if(quick_pow(a, phi_m, m) == 1) {	
                roots.push_back(a);				// 如果a^e=1(mod m)，是原根
            }
        }
    }
}

// 对于奇素数m，先求出一个原根和m-1的简化剩余系，然后生成所有原根
// 暴力判断出最小的原根g，大部分和find_roots相同
LL find_a_root(LL m, vector<int> prime, LL phi_m) {
    LL g;
    for(LL a = 1; a < m; a ++) {
        if(is_coprime(a, m, prime)) {
            bool flag = true;
            for(LL e = 1; e < phi_m; e ++) {
                if(quick_pow(a, e, m) == 1) {
                    flag = false;
                    break;
                }
            }
            if(!flag) continue;
            if(quick_pow(a, phi_m, m) == 1) {
                g = a;
                printf("找到一个原根g = %lld\n", g);
                return g;
            }
        }
    }
    return g;
}

// d遍历p-1的一个简化剩余系，那么g^d(mod p)遍历模p的所有原根
void find_roots_p(LL m, vector<int> prime, vector<LL> &roots, LL phi_m) {
    LL g = find_a_root(m, prime, phi_m);
    vector<LL> sim_m_1;
    for(LL i = 1; i < m - 1; i ++) {	    // 暴力求m-1的简化剩余系
        if(is_coprime(i, m - 1, prime)) {
            sim_m_1.push_back(i);
        }
    }
    for(auto d:sim_m_1) {					// 由m-1的简化剩余系生成所有原根
        roots.push_back(quick_pow(g, d, m));
    }
    sort(roots.begin(), roots.end());
}

给出m的简化剩余系

基础知识-一个原根→简化剩余系&所有原根节中写得应该很清楚了

1
2
3
4
5
6
7
// 由原根计算简化剩余系
void cal_sim(LL m, LL g, LL phi_m, vector<LL> &sim) {
    for(LL i = 0; i < phi_m; i ++) {
        LL ans = quick_pow(g, i, m);
        sim.push_back(ans);
    }
}

main函数代码

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
int main() {

    while(true) {
        LL m;
        vector<int> prime;

        printf("输入m的值(输入-1退出)：");
        cin >> m;
        if(m == -1) break;

        // 求出2~m中所有的素数
        Eratosthenes(m, prime);

        // 判断m有没有原根
        bool has_root = judge(m, prime);
        if(!has_root) {
            printf("该数没有原根\n");
            continue;
        } else {
            printf("该数存在原根\n");
        }

        // 求出φ(m)
        LL phi_m = Eular(m, prime);
        printf("求出φ(m) = %lld\n", phi_m);

        // 找原根
        vector<LL> roots;
        if(!prime[m] || m == 2) {
            find_roots(m, prime, roots, phi_m);
        } else {
            find_roots_p(m, prime, roots, phi_m);
        }
        printf("找到所有原根：\n");
        for(auto a:roots) {
            printf("%lld\t", a);
        }
        puts("");

        // 求简化剩余系
        vector<LL> sim;
        LL g = roots[0];
        cal_sim(m, g, phi_m, sim);
        printf("原根%lld生成的简化剩余系为：\n", g);
        for(auto a:sim) {
            printf("%lld\t", a);
        }
        puts("");

        sort(sim.begin(), sim.end());
        printf("排序后：\n");
        for(auto a:sim) {
            printf("%lld\t", a);
        }
        puts("");
    }

    return 0;
}

运行示例

m≠2,4,pα,2pαm\neq2,4,p^\alpha,2p^\alpha

m=p (奇素数)m=p\ (奇素数)

m=2,4,pα,2pαm=2,4,p^\alpha,2p^\alpha