手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

算法学习笔记(11): 原根

2023-01-16 22:06:55 来源：博客园

原根

此文相对困难，请读者酌情食用

在定义原根之前，我们先定义其他的一点东西

(相关资料图)

阶

通俗一点来说，对于 \(a\) 在模 \(p\) 意义下的阶就是 \(a^x \equiv 1 \pmod p\) 的最小正整数解\(x\)

或者说，\(a\) 在模 \(p\) 意义下生成子群的阶（群的大小）

再或者说，是 \(a\) 在模 \(p\) 意义下的循环节的大小

循环节，生成子群……真绕……其实两者很类似
两者的大小也就是在模 \(p\) 意义下集合 \(\{a^1, a^2, a^3,\dots,a^k\}\) 不重复元素的个数
可以通过欧拉定理可知 \(a^{\varphi(p)} \equiv a^0 \equiv 1 \pmod p\) 也就是说存在一个数 \(k\)，使得 \(a^k \equiv a \pmod p\)
所以，就有了循环……

我们将 \(a\) 在模 \(m\) 意义下的阶记作 \(ord_ma\)

显然，无论是根据群论还是什么，\(ord_ma\) 一定是 \(\varphi(p)\) 的因数

特别的，当 \(ord_ma = \varphi(p)\) 时，称 \(a\) 为模 \(p\) 意义下的一个原根

那么原根的定义出来了……

原根

上述定义或许不是那么简单，我们换一种说法

\[\begin{aligned}\forall x \in [1, \varphi(p)), a^x \not\equiv 1 \pmod p \\a^{\varphi(p)} \equiv 1 \pmod p\end{aligned}\]

满足上述两个条件的数 \(a\) 就是模 \(p\) 意义下的一个原根

这两个条件也是我们在程序中验证原根的方法 QwQ

而对于原根来说，\(a^1, a^2,\dots,a^{\varphi(p)}\) 在 \(m\) 下各不相同，他们就是最短的循环节，也是模 \(p\) 意义下的完全剩余系，或者说原根的生成子群

但是，并不是每一个数都存在原根

例如 \(\varphi(8) = 4\)，但是没有任何数在模 \(8\) 下的阶为 \(4\)

为判断一个数是否有原根，我们有一个重要的定理：

正整数 \(k\) 有原根的充要条件为 \(k\) 能表示成 \(2, 4, p^n, 2p^n\) 中的任何形式之一，其中 \(p\)为奇素数

由于证明比较复杂，若感兴趣可以参见这篇博客原根证明

那么如何求出一个数 \(p\) 有多少个原根

假设我们已经求出了一个原根 \(g\)

由于原根一定存在与 \(p\) 的完全剩余系中，而 \(g\) 的生成子群与之等价，也就是说，我们需要在

\[\{g^k|k \in [1, \varphi(p))\}\]

这个集合中寻找所有的原根

所以，考虑构造出判断阶的方法。我们令 \(d = gcd(k, \varphi(p))\)

那么

\[g^{k\frac {\varphi(p)} d} \equiv g^{\varphi(p) \frac kd} \equiv 1^{\frac kd} \equiv 1 \pmod p\]

那么 \(\frac k{gcd(k, \varphi(p))}\) 也就是 \(g^k\) 的阶

若需要满足原根的定义，我们必须使得 \(gcd(k, \varphi(p)) = 1\)

同时考虑 \(g = g^1\)，\(gcd(1, \varphi(p)) = 1\)，也就是说有总共有 \(\varphi(\varphi(p))\) 个原根

这同时启发我们，只要我们找到了任意一个模 \(p\) 意义下的原根，我们就可以求出所有原根。

至于如何找到原根，选择暴力枚举即可

有证明：如果一个数 \(n\) 有原根，则其最小原根在渐近意义下不大于 \(\sqrt[4]n\) 级别，所以直接枚举是没有任何问题的

那么我们总结一下求 \(n\) 的原根的所有步骤

预处理
- 利用线性筛求出所有的质数以及每一个数的 \(\varphi\) 值
- 对每一个筛出的质数，标记出所有 \(p^q\) 和 \(2p^q\) (别忘了\(2, 4\))
判断 \(n\) 是否有原根
求最小原根
- 求出 \(\varphi(m)\) 的所有质因数 \(i\)，记录 \(m/i\) （记得将 \(1\) 也记录进去）
- 枚举一个数 \(g\)，对于每一个记录的数 \(j = m/i\) 分别计算 \(g^j\)，如果\(i^j \equiv 1 \pmod m\) ，说明 \(i\) 不是原根（这里再下文中有解释）
- 重复第二部，直到找到一个原根 \(g\) 为止
求所有原根
- 枚举 \(k \in [1, \varphi(m))\)
- 如果 \(gcd(k, \varphi(m)) = 1\)，则 \(g^k\) 是一个原根，记录下他

解释：求最小原根的判断
为什么我们只需要枚举 \(m/i\) 就行了？
考虑我们将 \(m\) 分解成 \(m = i_1^{a_1} i_2^{a_2}\dots i_k^{a_k}\)
由于如果需要满足 \(i^j \equiv 1 \pmod p\)，一定有 \(j|\varphi(p)\)
那么对于 \(m/i = kj\)，一定有 \(i^{m/i}\equiv 1 \mod p\)
也就是说，所有 \(m/i\) 就包含了所有情况了
那么为什么要加上 \(1\) 呢，这就交给读者消化思考喽 ^_

参考代码如下：~~真的只供参考，这种写法特别慢~~

templateinline T gcd(T x, T y) {T z;while (y) z = x % y, x = y, y = z;return x;}templateinline T qpow(T a, T x, T p) {T r(1); a %= p;while (x) {if (x & 1) r = (r * a) % p;a = (a * a) % p, x >>= 1;}return r;}int phi[N], notp[N];std::vector prm;void getPrm() {phi[1] = 1;for (int i = 2; i < N; ++i) {if (!notp[i]) prm.push_back(i), phi[i] = i - 1;for (const int &j : prm) {if (i * j >= N) break;notp[i * j] = true;if (i % j == 0) {// i | n && i^2 | n => phi(n) = phi(n / i) * iphi[i * j] = phi[i] * j; break;} else {// i | n && not i^2 | n => phi(n) = phi(n / i) * (i - 1)phi[i * j] = phi[i] * phi[j];}}} // end getPrm for}bool exists[N];void getExists() {exists[2] = exists[4] = true;for (int i = 1; i < (int)prm.size(); ++i) {int p = prm[i];for (int q = p; q < N; q *= p) {exists[q] = true;if (q * 2 < N) exists[q * 2] = true;}}// printf("Exists init!\n");}void factorize(int x, vector & v) {v.push_back(1);for (const int &p : prm) {if (p >= x) break;if (x % p == 0) v.push_back(x / p);}}void getAll(int p, vector & v) {// no answerif (!exists[p]) return;int ph = phi[p];int fst, cur;vector factors; factors.clear();factorize(ph, factors);// enum i which gcd(i, m) == 1// find first element i suit i^ph = 1 mod pfor (int i = 1; ; ++i) {if (gcd(i, p) != 1) continue;// if (qpow(i, ph, p) != 1) continue;bool valid = true;// we need i only if i^ph = 1 mod p, not other numbers.for (auto &e : factors) {if (e != ph && qpow(i, e, p) == 1) {valid = false; break;}}if (valid) {fst = cur = i; break;}}for (int i(1); i <= ph; ++i) {if (gcd(i, ph) == 1) v.push_back(cur);cur = cur * fst % p;}}

考虑模板可能有爆 int 的风险，请参考者合理使用 long long

这样通过 getAll得出的 vector是乱序的，需要再排序一次

关键词：也就是说完全剩余系正整数解