k次单位根的平方是k/2次单位根

Last updated on Nov 12, 2025

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

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

\set{1,\omega,\omega^2,\omega^3,\omega^4,\omega^5}

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

\set{1^2,\omega^2,\omega^4,\omega^6,\omega^8,\omega^{10}}

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

\set{1^2,\omega^2,\omega^4,\omega^6,(\omega^6)\omega^2,(\omega^{6})\omega^4}

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

\set{1^2,\omega^2,\omega^4,1,(1)\omega^2,(1)(\omega^4)}

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

\set{1^2,\omega^2,\omega^4,1,\omega^2,\omega^4}

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

\set{1,\omega^2,\omega^4}

新集合的大小是原集合的一半，且每个元素都是 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\}$ 。我们将该子群的所有元素平方如下：

\begin{aligned} &1^2 = 1\pmod{17},\\ &9^2 \equiv 13\pmod{17},\\ &13^2 \equiv 16\pmod{17} ,\\ &15^2 \equiv 4\pmod{17},\\ &16^2 \equiv 1\pmod{17},\\ &8^2 \equiv 13\pmod{17},\\ &4^2 \equiv 16\pmod{17},\\ &2^2 = 4\pmod{17}. \end{aligned}

平方后得到的集合是 $\{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$ ：

\set{\omega^0,\omega^1,\omega^2,...}\quad\set{\omega^{k/2},\omega^{k/2+1},\omega^{k/2+2},...}

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

\set{\omega^0,\omega^1,\omega^2,...}\quad\set{-\omega^0,-\omega^1,-\omega^2,...}

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

\set{1,\omega^2,\omega^4,...}\quad\set{1,\omega^2,\omega^4,...}

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

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

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

(a^2)^{\frac{k}{2}}\equiv 1

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

(a^2)^{\frac{k}{2}} = a^{k}

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

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

Last updated on Nov 12, 2025

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

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

\set{1,\omega,\omega^2,\omega^3,\omega^4,\omega^5}

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

\set{1^2,\omega^2,\omega^4,\omega^6,\omega^8,\omega^{10}}

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

\set{1^2,\omega^2,\omega^4,\omega^6,(\omega^6)\omega^2,(\omega^{6})\omega^4}

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

\set{1^2,\omega^2,\omega^4,1,(1)\omega^2,(1)(\omega^4)}

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

\set{1^2,\omega^2,\omega^4,1,\omega^2,\omega^4}

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

\set{1,\omega^2,\omega^4}

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

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

更多示例：

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

8 次单位根平方的示例

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

\begin{aligned} &1^2 = 1\pmod{17},\\ &9^2 \equiv 13\pmod{17},\\ &13^2 \equiv 16\pmod{17} ,\\ &15^2 \equiv 4\pmod{17},\\ &16^2 \equiv 1\pmod{17},\\ &8^2 \equiv 13\pmod{17},\\ &4^2 \equiv 16\pmod{17},\\ &2^2 = 4\pmod{17}. \end{aligned}

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

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

k 必须为偶数

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

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

\set{\omega^0,\omega^1,\omega^2,...}\quad\set{\omega^{k/2},\omega^{k/2+1},\omega^{k/2+2},...}

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

\set{\omega^0,\omega^1,\omega^2,...}\quad\set{-\omega^0,-\omega^1,-\omega^2,...}

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

\set{1,\omega^2,\omega^4,...}\quad\set{1,\omega^2,\omega^4,...}

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

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

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

(a^2)^{\frac{k}{2}}\equiv 1

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

(a^2)^{\frac{k}{2}} = a^{k}

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

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