NTT 简单入门

七海

算法数学

发布于：2021年7月12日

次浏览

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

一句话简介：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})\) 的。完整代码如下：

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\) 似乎会暴毙……

阶和原根

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

后记

参考资料

更新于：2021年7月12日

算法

ACM

数论

FFT

NTT

简单数学：从约数个数和到莫比乌斯反演

差不多算是基础的程度的知识的数论能力，就算已经不参加弹幕神乐的巫女想必也是应该要掌握的吧。首先来点题目链接：P3327【SDOI2015】约数个数和 - 洛谷 | 2185. 「SDOI201...

数论分块入门

《退役人的自我救赎系列》——其一，也就是基础的数论知识。整除分块求解 \(\sum_{i=1}^n \frac{n}i\) 的值，\(n\) 是 \(10^{10}\) 级别。暴力是 ...