原根¶
整数的次数¶
设 \(m>0\)，\((a, m) = 1\)，\(l\) 是使
成立的最小正整数，则 \(l\) 是 \(a\) 对模数 \(m\) 的原根。
定理 2：设 \(a\) 对模数 \(m\) 的次数为 \(l\)，则
对模数 \(m\) 两两不同余。
定理 3：设 \(a\) 对模数 \(m\) 的次数为 \(l\)，\(\lambda > 0\)，\(a^\lambda\) 对模数 \(m\) 的次数为 \(l_1\)，则 \(l_1 = \dfrac{l}{(\lambda, l)}\)。
推论：设 \(a\) 为对模数 \(m\) 的次数为 \(l\)，则 \(\varphi(l)\) 个数
对模数 \(m\) 的次数均为 \(l\)。
定理 4：设 \(p\) 是一个素数，如果存在整数 \(a\)，它对模数 \(p\) 的次数是 \(l\)，则恰有 \(\varphi(l)\) 个对模数 \(p\) 两两不同余的整数，它们对模数 \(p\) 的次数都为 \(l\)。
定理 5：设 \(l \mid p -1\)，则次数为 \(l\) 的，模数 \(p\) 互不同余的整数的个数是 \(\varphi(l)\) 个。
原根¶
定义：设整数 \(m>0\)，\((g, m) = 1\)，如果整数 \(g\) 对 \(m\) 的次数是 \(\varphi(m)\)，则 \(g\) 叫做 \(m\) 的一个原根。
定理 1：设 \((g, m) = 1\)，\(m>0\)，则 \(g\) 是 \(m\) 的一个原根的充分必要条件是
组成模数 \(m\) 的一组缩系。
定理 2：设 \(m > 1\)，若 \(m\) 有原根，则 \(m\) 必为下列诸数之一：
这里 \(l \ge 1\)，\(p\) 为奇素数。
定理 3：\(m = 2, 4, p^l, p^{2l}\)（\(l\ge 1\)， \(p\) 为奇素数）时，\(m\) 有原根。
引理：设 \(g\) 是奇素数 \(p\) 的一个原根，满足
则对于每一个 \(a \ge 2\)，有
定理 4：设 \(m\) 有一个原根 \(g\)，则 \(m\) 恰有 \(\varphi(\varphi(m))\) 个对模数 \(m\) 互不同余的原根，它们是由集
中的数给出。
次数的计算¶
定理 1：如果 \(m = p_1^{l_1}\ldots p_k^{l_k}\) 是 \(m\) 的标准分解式，整数 \(a\) 对模数 \(m\) 的次数等于整数 \(a\) 对模数 \(p_i^{l_i}\ (i=1, \ldots, k)\) 的诸次数的最小公倍数。
定理 2：设 \(p\) 是一个素数，\(a\) 对模数 \(p^j\) 的次数是 \(f_j\)，又设 \(p_i \mid\mid a^{f_2} - 1\)，有
原根的计算¶
定理 1：设 \(m>2\) ，\(\varphi(m)\) 的所有不同的素因子是 \(q_1, q_2, \ldots, q_s\)，\((g, m) = 1\)，则 \(g\) 是 \(m\) 的一个原根的充分必要条件是
定理 2：设 \(a\) 对模数奇素数 \(p\) 的次数是 \(d\)，\(d<p-1\)，则
都不是 \(p\) 的原根。
要求出原根，先列出各数
取 \(a=2\)，计算 \(2\) 对 \(p\) 的次数 \(d\)，如果 \(d = p-1\)，\(2\) 就是 \(p\) 的原根。如果 \(d < p-1\)，在上式中除去下列各数：
在上式中再取一数，重复上述方法，直到剩下 \(\varphi(p-1)\) 个数，这些数都是 \(p\) 的原根。
int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
int powmod(int a, int b, int p) {
int res = 1;
while (b > 0) {
if (b & 1) res = res * a % p;
a = a * a % p, b >>= 1;
}
return res;
}
// Finds the primitive root modulo p
int generator(int p) {
vector<int> fact;
int phi = p - 1, n = phi;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
fact.push_back(i);
while (n % i == 0) n /= i;
}
}
if (n > 1) fact.push_back(n);
for (int res = 2; res <= p; ++res) {
bool ok = true;
for (int factor : fact) {
if (powmod(res, phi / factor, p) == 1) {
ok = false;
break;
}
}
if (ok) return res;
}
return -1;
}
// This program finds all numbers x such that x^k=a (mod n)
int main() {
int n, k, a;
scanf("%d %d %d", &n, &k, &a);
if (a == 0) return puts("1\n0"), 0;
int g = generator(n);
// Baby-step giant-step discrete logarithm algorithm
int sq = (int)sqrt(n + .0) + 1;
vector<pair<int, int>> dec(sq);
for (int i = 1; i <= sq; ++i)
dec[i - 1] = {powmod(g, i * sq * k % (n - 1), n), i};
sort(dec.begin(), dec.end());
int any_ans = -1;
for (int i = 0; i < sq; ++i) {
int my = powmod(g, i * k % (n - 1), n) * a % n;
auto it = lower_bound(dec.begin(), dec.end(), make_pair(my, 0));
if (it != dec.end() && it->first == my) {
any_ans = it->second * sq - i;
break;
}
}
if (any_ans == -1) return puts("0"), 0;
// Print all possible answers
int delta = (n - 1) / gcd(k, n - 1);
vector<int> ans;
for (int cur = any_ans % delta; cur < n - 1; cur += delta)
ans.push_back(powmod(g, cur, n));
sort(ans.begin(), ans.end());
printf("%d\n", ans.size());
for (int answer : ans) printf("%d ", answer);
}s原根的一个性质¶
定理 1：设 \(p\) 是一个奇素数，\(\mathrm Q(p)\) 表示 \(p\) 的 互不同余的 \(\varphi(p-1)\) 个原根的和，我们有
其中\(\mu(\cdot)\)表示莫比乌斯函数。
定理 2：设 \(p\) 为一个奇素数，对模数 \(p\) 的次数为 \(d\) 的 \(\varphi(d)\) 个互不同余的数的 \(r\) 次幂的和为 \(S\)，则
这里 \(d_1 = \dfrac{d}{(r, d)}\)。