NTT 简单入门

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

一句话简介：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$ 的一个原根。

性质

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

定理

原根的存在条件

判断对于一个整数$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$ 似乎会暴毙……

阶和原根

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

后记

参考资料

• 题解 P3803 【【模板】多项式乘法（NTT）】2 - attack 的博客 - 洛谷博客 (luogu.com.cn)
• 快速数论变换（NTT）超详解 - 知乎 (zhihu.com)
• 阶与原根 - 知乎 (zhihu.com)
• 算法学习笔记(40): 原根 - 知乎 (zhihu.com)