抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

七つの海

ひと結び、人を結んで

《退役人的自我救赎系列》——其二,也就是差不多算是初等数论的知识。

一句话简介:NTT 即快速数论变换,是一种可以在 \(n\log n\) 的时间内完成多项式乘法的算法——的一部分。

前置知识

FFT

可以看我之前写过的一篇文章:基础知识:FFT - 简单入门 - 七海の参考書 (shiraha.cn)

FFT 需要使用复数——这样就无法回避大量的浮点运算,然后精度就会爆炸;但是由于已经证明了在复数域内,具有循环卷积特性的唯一变换是DFT,所以在复数域中不存在具有循环卷积性质的更简单的离散正交变换;因此,我们就提出了以数论为基础的具有循环卷积性质的快速数论变换NTT):它的特点在于用有限域上的单位根来取代复平面上的单位根。

上面这段话是上网抄的。虽然我现在还理解不了,但是有一件事情十分清楚——和 FFT 利用单位根的性质减少运算量一样,NTT 利用了原根的性质来减少运算量,达到了同样的复杂度。

定义

\(a, p\in\N^+\) 满足 \(\gcd(a, p)=1\)\(p>1\),那么:

对于使得 \(a^n \equiv 1\ \text{mod}\ p\) 成立的最小的 \(n\),我们称之为 \(a\)\(p\) 的阶,记作 \(\delta_p(a)\)\(\text{ord}_pa\)

性质

1. 对于 \(i\in[0, \delta_p(a))\),所有的 \(a_i\ \text{mod}\ p\) 都互不相同

反证法:令有 \(j\ne k\) 在该范围内并且模意义下相同,那么显然有 \(a^{|j-k|}\equiv1\ \text{mod}\ p\),且 \(|j-k|\) 也属于该范围内,和定义矛盾。

2. 对于任何 \(a^n \equiv 1\ \text{mod}\ p\),有 \(\delta_p(a) \mid n\)

显然。否则,把 \(n\) 表示为 \(k\delta_p(a) + m\),显然 \(m \in (0, \delta_p(a))\) 且满足 \(a^m \equiv 1\ \text{mod}\ p\),和性质 1 冲突。

推论 1:若有 \(\gcd(a, p)=1\),那么 \(\delta_p(a) \mid \phi(p)\)

由欧拉定理可知:若 \(\gcd(a, p) = 1\),则 \(a^{\phi(p)} \equiv 1 \ \text{mod} \ p\)。那么由性质 2 可得 \(\delta_p(a) \mid \phi(p)\)

3. 若 \(q\in\Z^+\)\(p\) 是素数,那么 \(\delta_p(q^i)=\delta_p(q) \iff \gcd(\delta_p(q), i)=1\)

首先,我们记 \(q^i = q^{\gcd(\delta_p(q), i)\cdot r}\),显然 \(r=\frac i{\gcd(\delta_p(q), i)} \in\Z^+\)

由性质 2 和题设条件欧拉函数的性质,可得:\(\delta_p(q) \mid \phi(p) = (p-1)\) (好像没用)

那么,有:\((g^i)^{\frac{\delta_p(q)}{\gcd(\delta_p(q), i)}}=(g^{\delta_p(q)})^{\frac i{\gcd(\delta_p(q), i)}}=g^{r\cdot \delta_p(q)}\equiv1\ \text{mod}\ p\)


假设 \(\gcd(\delta_p(q), i)\ne1\),那么 \(\gcd(\delta_p(q), i)>1\),那么 \(\frac{\delta_p(q)}{\gcd(\delta_p(q), i)}<\delta_p(q)\)

因为 \((g^i)^{\frac{\delta_p(q)}{\gcd(\delta_p(q), i)}}\equiv1\ \text{mod}\ p\),由性质 2 可得 \(\delta_p(q^i)\mid\frac{\delta_p(q)}{\gcd(\delta_p(q), i)}\),因此 \(\delta_p(q^i)\le\frac{\delta_p(q)}{\gcd(\delta_p(q), i)}\)

综上所述,可得:\(\delta_p(q^i)\le\frac{\delta_p(q)}{\gcd(\delta_p(q), i)}<\delta_p(q)\)

\(\gcd(\delta_p(q), i)\ne1\Rightarrow \delta_p(q^i)\ne\delta_p(q)\)必要条件得证。


继承上述的证明,若有 \(\gcd(\delta_p(q), i)=1\),那么 \(\frac{\delta_p(q)}{\gcd(\delta_p(q), i)}=\delta_p(q)\)

由上述证明就可以得到:\(\delta_p(q^i)\le\delta_p(q)\)

因为 \(g^{i\cdot\frac{\delta_p(q)}{\gcd(\delta_p(q), i)}}\equiv1\ \text{mod}\ p\),和性质 2 和 4 可知:\(\delta_p(q)\mid i\cdot\delta_p(q^i)\)

因为 \(\gcd(\delta_p(q), i)=1\),所以 \(上式\Rightarrow\delta_p(q)\mid \delta_p(q^i)\),也就是 \(\delta_p(q)\le\delta_p(q^i)\)

综上所述,\(\because \delta_p(q^i)\le\delta_p(q) \and \delta_p(q)\le\delta_p(q^i)\)\(\therefore \delta_p(q)=\delta_p(q^i)\)

\(\gcd(\delta_p(q), i)=1\Rightarrow \delta_p(q^i)=\delta_p(q)\)充分条件得证。


综上所述,\(\gcd(\delta_p(q), i)=1\)\(\delta_p(q)=\delta_p(q^i)\)充分必要条件

4. \(\delta_p(a^b) = \frac{\delta_p(a)}{\gcd(\delta_p(a), b)}\),其中 \(a, p, b \in \Z^+\)

由阶的定义可知:\((a^b)^{\delta_p(a^b)} \equiv a^{b\cdot\delta_p(a^b)}\equiv1\ \text{mod} \ p\)

又由性质 2,可以得到:\(\delta_p(a)\mid b\cdot\delta_p(a^b) \Rightarrow \frac{\delta_p(a)}{\gcd(\delta_p(a), b)}\mid \frac{b}{\gcd(\delta_p(a), b)}\cdot\delta_p(a^b)\)

显然,因为 \(\gcd(\frac{\delta_p(a)}{\gcd(\delta_p(a), b)}, \frac{b}{\gcd(\delta_p(a), b)})=1\),因此:\(上式\Rightarrow \frac{\delta_p(a)}{\gcd(\delta_p(a), b)}\mid\delta_p(a^b)\)

又因为定义:\(a^{b\cdot\frac{\delta_p(a)}{\gcd(\delta_p(a), b)}}\equiv a^{\delta_p(a)\cdot\frac{b}{\gcd(\delta_p(a), b)}} \equiv 1\ \text{mod}\ p\)\(\frac{b}{\gcd(\delta_p(a), b)}\) 显然是整数。

所以由性质 2 可得:\(\delta_p(a^b)\mid\frac{\delta_p(a)}{\gcd(\delta_p(a), b)}\)

综上所述:\(\because \frac{\delta_p(a)}{\gcd(\delta_p(a), b)}\mid\delta_p(a^b)\ \and\ \delta_p(a^b)\mid\frac{\delta_p(a)}{\gcd(\delta_p(a), b)}\)\(\therefore \delta_p(a^b)=\frac{\delta_p(a)}{\gcd(\delta_p(a), b)}\)

5. \(p \in \N^+,\ a, b\in\Z\)\(\gcd(a, p) = \gcd(b, p) = 1\),那么 \(\gcd(\delta_p(a),\delta_p(b))=1\) \(\iff\) \(\delta_p(ab)=\delta_p(a)\delta_p(b)\)

由定义可得 \(a^{\delta_p(a)}\equiv1\ \text{mod}\ p\)\(b^{\delta_p(b)}\equiv1\ \text{mod}\ p\),那么:\((ab)^{\text{lcm}(\delta_p(a),\delta_p(b))}\equiv1\ \text{mod}\ p\)

由性质 2,可得:\(\delta_p(ab)\mid\text{lcm}(\delta_p(a),\delta_p(b))\)

\(\delta_p(ab)=\delta_p(a)\delta_p(b)\) 成立,那么:\(上式 \Rightarrow \delta_p(a)\delta_p(b)\mid\text{lcm}(\delta_p(a),\delta_p(b))\)

又因为 \(\text{lcm}(\delta_p(a),\delta_p(b)) = \frac{\delta_p(a)\delta_p(b)}{\gcd(\delta_p(a),\delta_p(b))}\),可得 \(\gcd(\delta_p(a),\delta_p(b))=1\)

\(\delta_p(ab)=\delta_p(a)\delta_p(b)\) \(\Rightarrow\) \(\gcd(\delta_p(a),\delta_p(b))=1\)必要性得证。


又由阶的定义:\((ab)^{\delta_p(ab)}\equiv1\ \text{mod}\ p\),可以进行如下推导: \[ (ab)^{\delta_p(ab)}\equiv(ab)^{\delta_p(ab)\delta_p(b)}\equiv a^{\delta_p(ab)\delta_p(b)}\cdot b^{\delta_p(ab)\delta_p(b)}\equiv a^{\delta_p(ab)\delta_p(b)}\cdot 1\equiv1\ \text{mod}\ p \] 由性质 2,可得:\(\delta_p(a)\mid\delta_p(ab)\delta_p(b)\);因为 \(\gcd(\delta_p(a),\delta_p(b))=1\),所以 \(\delta_p(a)\mid\delta_p(ab)\)

同理,可得:\(\delta_p(b)\mid\delta_p(ab)\);因为 \(\gcd(\delta_p(a),\delta_p(b))=1\),所以 \(\delta_p(a)\delta_p(b)\mid\delta_p(ab)\)

由定理可得:\(a^{\delta_p(a)}\equiv a^{\delta_p(a)\delta_p(b)}\equiv1\ \text{mod}\ p\)\(b^{\delta_p(b)}\equiv b^{\delta_p(a)\delta_p(b)}\equiv1\ \text{mod}\ p\),因此: \[ a^{\delta_p(a)\delta_p(b)} \cdot b^{\delta_p(a)\delta_p(b)} \equiv (ab)^{\delta_p(a)\delta_p(b)} \equiv1\ \text{mod}\ p \] 由性质 2,可得 \(\delta_p(ab)\mid\delta_p(a)\delta_p(b)\);因此,可证 \(\delta_p(ab)=\delta_p(a)\delta_p(b)\)

\(\gcd(\delta_p(a),\delta_p(b))=1\) \(\Rightarrow\) \(\delta_p(ab)=\delta_p(a)\delta_p(b)\)充分性得证。


综上所述:\(\gcd(\delta_p(a),\delta_p(b))=1\)\(\delta_p(ab)=\delta_p(a)\delta_p(b)\)充分必要条件

原根

定义

\(m \in \N^+,g\in\Z\),若有 \(\delta_m(g)=\phi(m)\)\(\gcd(m,g)=1\),那么称 \(g\) 是模 \(m\) 的一个原根。

若整数 \(g\) 模正整数 \(m\) 的阶(这要求它们互质)和 \(\phi(m)\) 相等,那么 \(g\) 是模 \(m\) 的一个原根。

性质

……我一定是哪里变得奇怪了才会想着抄录全部性质并键证它们== 哪天闲的没事干再补全吧()

7Q6A_S_AWQFY__Q5NEZI_E.jpg

定理

原根的存在条件

判断对于一个整数 \(p\) 是否存在原根:

  • 对于整数 \(p=2,4\),它们的原根显然存在
  • 奇素数 \(p\) 的原根存在;对于 \(\alpha\in\N^+\)\(p^\alpha\) 的原根存在
  • 对于奇素数 \(p\)\(\alpha\in\N^+\)\(2p^\alpha\) 的原根存在
  • \(p\) 不符合上述的任何条件,则对于 \(\forall a\in\Z\)\(\gcd(a, p)=1\),都有 \(\delta_p(a) < \phi(p)\),即 \(p\) 不存在原根

与之相关的一些定理:

  • 对于奇素数 \(p\),若 \(g\) 是其原根,则 \(g\) 或者 \(g+p\)\(p^2\) 的原根
  • 对于奇素数 \(p\)\(\alpha \in \N^+\),若 \(g\) 是模 \(p^\alpha\) 的原根,则 \(g\) \(g+p^\alpha\) 中的奇数是 \(2p^\alpha\) 的原根

简单地说,对于奇素数 \(p\)\(\alpha\in\N^+\),有原根的数包括:\(\{2,4,p^\alpha,2p^\alpha\}\)

求法

对于一个数 \(n\),如果它存在原根,那么首先找到它的最小原根并令其为 \(g\);那么,\(n\) 的所有原根都可以表示为 \(g^k\)\(k\) 是正整数并且满足 \(\gcd(\phi(n),k)=1\),共 \(\phi(\phi(n))\) 个。

最小原根 \(g\) 的大小已经证明是不会超过 \(\sqrt[4]{n}\) 的,所以可以通过暴力枚举来确定,然后按照定义要求来验证某个数字是否是原根——但是定义要求 \(\delta_n(g)=\phi(n)\),我们无法对于每一个备选 \(g\) 都枚举 \(i\in[1,\phi(n))\) 来计算 \(g^i\),观察它不和 \(1\) 同余来判定它是阶。

注意到阶的性质 2 的推论 1,我们可以知道 \(\delta_n(g)\mid\phi(n)\);也就是说,对于备选 \(g\),如果它模 \(n\) 下的阶不满足原根的要求,而是另有 \(k < \phi(n)\) 存在,那么它满足 \(k\mid\phi(n)\);那么,我们只需要检查 \(\phi(n)\) 的所有因数就可以找到可能存在的 \(k\) 了,而不需要枚举整个 \([1,\phi(n))\);具体地,若 \(\phi(n)\) 的质因子被记为 \(p_1,\dots,p_r\),那么实际上我们只需要检查所有的 \(\frac{\phi(n)}{p_i}\) 即可——它覆盖了所有的真因数的倍数,检查它们等同于检查了所有的真因数。

综上所述,找到最小原根 \(g\) 所需要的时间是 \(\mathcal{O}(\sqrt[4]n\cdot\log n)\) 的;利用最小原根 \(g\) 求出所有原根所需要的时间是 \(\mathcal O (\phi(n)\cdot\log n^{\frac{\phi(n)}4})\) 的。完整代码如下:

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
template<int n>
auto &linear_sieve() {
static vector<int> prime;
static array<int, n + 1> vis;
for (int i = 2; i <= n; ++i) {
if (!vis[i])
prime.push_back(i), vis[i] = i;
for (auto &pp : prime) {
if ((llong) i * pp > n) break;
vis[i * pp] = pp;
if (i % pp == 0) break;
}
}
static auto ret = make_pair(ref(prime), ref(vis));
return ret;
}

llong fast_pow(llong a, llong b, llong mod) {
llong ans = 1;
while (b) {
if (b & 1u) ans = (ans * a) % mod;
a = (a * a) % mod, b >>= 1u;
}
return ans % mod;
}

constexpr int N = 1e6 + 5;

bool check_primitive_root(
const set<int> &de, llong g,
llong phi, llong n) {
if (fast_pow(g, phi, n) == 1) {
return none_of(de.begin(), de.end(), [&](int p) {
return fast_pow(g, phi / p, n) == 1;
});
} else return false;
}

signed main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
const auto [p, dc] = linear_sieve<N>();
const auto decompose = [&dc = dc]
(llong x, set<int> &de) {
de.clear();
for (auto ii = x; ii > 1;) {
de.insert(dc[ii]);
ii /= dc[ii];
}
};
bitset<N> has_primitive_root;
has_primitive_root.set(1).set(2).set(4);
for (llong pp : p) {
if (pp == 2) continue;
for (auto now = pp; now < N; now *= pp) {
has_primitive_root.set(now);
if (now * 2 < N) has_primitive_root.set(now * 2);
}
}
vector<llong> ans;
for (auto T = read(); T--;) {
auto n = read(), d = read(), phi = n;
if (has_primitive_root[n]) {
set<int> de_n, de_phi;
decompose(n, de_n);
for (auto pi : de_n)
(phi /= pi) *= (pi - 1);
decompose(phi, de_phi);
llong g = 0, lim = n;
for (int i = 1; i <= lim; ++ i)
if (check_primitive_root(de_phi, i, phi, n))
{ g = i; break; }
if (!g) {
cout << 0 << endl << endl;
continue;
}
ans.clear();
for (auto gi = g, i = 1ll;
i <= phi; ++ i, (gi *= g) %= n) {
if (gcd(i, phi) == 1)
ans.push_back(gi);
}
sort(ans.begin(), ans.end());
cout << ans.size() << endl;
for (auto id = d - 1; id < ans.size(); id += d)
cout << ans[id] << ' ';
cout << endl;
} else cout << 0 << endl << endl;
}
return 0;
}

首先筛出质数,再筛出所有的可能有原根的数——这一步是 \(\mathcal O (n\log n)\) 的;对于一个有原根的数 \(n\),首先利用筛的结果(当然也可以直接用线性筛直接算好了存起来)根据定义求出 \(\phi(n)\),然后再利用筛维护的数据(或者埃氏筛直接存起来)分解其质因数存好备用;暴力枚举,并且利用上面说的方法来检查其是否为原根,求出最小原根——这一步是理论 \(\mathcal O (\sqrt[4]n\log n)\) 的;最后再利用最小原根生成所有的原根:这需要重复 \(\phi(n)\) 次,每次使用 \(\gcd\) 检查——这一步是 \(\mathcal O(\phi(n)\log n)\) 的。

上面的代码可以通过 P6091 【模板】原根。需要注意虽然最小原根有这个理论界限,但是求的时候只遍历到 \(\lceil n^\frac14\rceil\) 似乎会暴毙……

阶和原根

那么如何理解这两个抽象的概念呢?

后记

参考资料

评论