如果我们取 $k$ 次单位根的集合（其中 $k$ 为偶数）并将每个元素平方，所得集合的大小将是原来的一半。新集合将是 $\frac{k}{2}$ 次单位根的集合。

例如，假设 $k = 6$。6 次单位根将是

如果我们将每个元素平方，我们会得到以下集合。有些元素的指数大于或等于 $k$，但我们将在下一步中处理这个问题。

然后我们可以将指数拆分如下：

由于 $\omega$ 是 6 次单位根，$\omega^6\equiv1$，因此我们有：

消除乘以 $1$ 的操作后，我们得到

现在将所有重复的项替换为单个元素：

新集合的大小是原集合的一半，且每个元素都是 3 次单位根：

• $1^3\equiv1$
• $(\omega^2)^3=\omega^6\equiv1$
• $(\omega^4)^3=\omega^{12}=\omega^6\omega^6\equiv1\cdot1=1$

如果我们将 6 次单位根绘制在一个圆上，我们可以看到平方操作“移除”了每隔一个的元素。我们从 $\set{1,\omega,\omega^2,\omega^3,\omega^4,\omega^5}$ 开始，最终得到 $\set{1,\omega^2,\omega^4}$

重申一下，如果我们取 $k$ 次单位根的集合，且 $k$ 为偶数，然后将每个元素平方，我们会得到一个大小减半的集合，其中每个元素都是 $\frac{k}{2}$ 次单位根。

更多示例：

• 如果 $k = 10$，我们将每个 10 次单位根平方，我们会得到一个大小为 5 的集合，即 5 次单位根。
• 如果 $k = 8$，我们将每个 8 次单位根平方，我们会得到一个大小为 4 的集合，即 4 次单位根。
• 如果 $k = 4$，我们将每个 4 次单位根平方，我们会得到一个大小为 2 的集合，即 2 次单位根。
• 如果 $k = 2$，我们将每个 2 次单位根平方，我们会得到一个大小为 1 的集合，其中只有元素 1。

最后一点很容易说明。2 次单位根是 1 的平方根，始终为 $\set{1,-1}\equiv\set{1,\omega^{k/2}}$。1 的平方是 1，-1 的平方也是 1。等价地，$(\omega^{k/2})^2=\omega^k\equiv1$。

8 次单位根平方的示例

考虑有限域 $\mathbb{F}_{17}$ 中 8 次单位根的子群 $\langle 9\rangle = \{1, 9, 13, 15, 16, 8, 4, 2\}$。我们将该子群的所有元素平方如下：

平方后得到的集合是 $\{1,13,16,4\}$，这恰好是 4 次单位根的子群。

这是平方前后单位根的可视化。我们从集合 $\set{1, 9, 13, 15, 16, 8, 4, 2}$ 开始，最终得到集合 $\set{1,13,16,4}$

k 必须为偶数

如果 $k$ 为奇数，那么就不存在“群的一半”这种说法，因为奇数大小的集合无法被分为两半。出于 NTT 的目的，我们只处理偶数大小的 $k$，因此我们对 $k$ 为奇数的情况不感兴趣。

新集合大小减半这一主张的证明

设 $\omega$ 为本原 $k$ 次单位根，且 $k$ 为偶数。设 $\langle\omega\rangle$ 为由 $\omega$ 生成的阶数为 $k$ 的子群。我们主张 $|\set{\omega^2|\omega\in\langle\omega\rangle}|=k/2$。

证明实际上非常简单直观。

我们在前面的章节中已经确定了 $\omega^{i}$ 和 $\omega^{i+k/2}$ 是加法逆元。由于 $k$ 为偶数，我们可以将该群划分为两个集合，第一个集合为 $0...(k/2-1)$，第二个集合为 $k/2...k-1$：

这些元素同余于以下表示形式：

如果我们将 $f(x)=x^2$ 应用于这两个集合，我们会得到两个内容完全相同且大小为 $k/2$ 的集合：

由于这两个集合完全相同，因此这两个集合的并集大小也将相同，即为 $k/2$。

k 次单位根平方产生 k/2 次单位根的证明

假设 $a$ 是 $k$ 次单位根。我们的目的是证明 $a^2$ 是 $\frac{k}{2}$ 次单位根，也就是说：

让我们化简 $(a^2)^{\frac{k}{2}}$：

由于 $a^k\equiv1$（因为 $a$ 是 $k$ 次单位根），因此可以得出 $(a^2)^{\frac{k}{2}}\equiv 1$。

因此，$a^2$ 确实是 $\frac{k}{2}$ 次单位根。