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

如果我们取 -th 个单位根的集合（其中 为偶数），并将每个元素平方，结果集合的大小将是原来的一半。新的集合将是 -th 个单位根。

例如，假设 。那么第 6 个单位根是

如果我们把每个元素平方，会得到下面的集合。有些元素的指数大于等于 ，但我们会在下一步处理它。

我们可以将指数分解如下：

因为 是第 6 个单位根，所以 ，因此我们有：

移除乘以 的部分，我们得到

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

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

如果我们在一个圆上绘制第 6 个单位根，我们可以看到平方“移除”了每隔一个元素。我们从 开始，以 结束

重申一下，如果我们取 -th 个单位根的集合，并且 是偶数，然后对每个元素进行平方，我们会得到一个大小为原来一半的集合，其中每个元素都是 -th 个单位根。

更多例子：

• 如果 并且我们对每个第 10 个单位根进行平方，我们会得到一个大小为 5 的集合，这些集合是第五个单位根。
• 如果 并且我们对每个第 8 个单位根进行平方，我们会得到一个大小为 4 的集合，这个集合是第四个单位根。
• 如果 并且我们对每个第 4 个单位根进行平方，我们会得到一个大小为 2 的集合，这个集合是第二个单位根。
• 如果 并且我们对每个第 2 个单位根进行平方，我们会得到一个大小为 1 的集合，这个集合只有元素 1。

最后一点很容易说明。第二个单位根是 1 的平方根，始终是 。对 1 平方得到 1，对 -1 平方得到 1。等效地，。

对第 8 个单位根进行平方的示例

考虑有限域 中第 8 个单位根的子群 。我们对这个子群的所有元素进行平方，如下所示：

平方后得到的集合是 ，这恰好是第 4 个单位根的子群。

这是平方前后单位根的可视化。我们从集合 开始，以集合 结束

k 必须是偶数

如果 是奇数，那么就不存在所谓的“群的一半”，因为奇数大小的集合不能被分成两份。为了 NTT 的目的，我们只处理偶数大小的 ，所以我们对 是奇数的情况不感兴趣。

关于新集合大小是原来一半的主张的证明

设 是一个本原 -th 单位根，其中 是偶数。设 是由 生成的阶数为 的子群。我们声称 。

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

我们在前面的章节中已经确定 和 是加法逆元。由于 是偶数，我们可以将群分为两个集合，第一个是 ，第二个是 ：

这些元素与以下表示形式一致：

如果我们对两个集合都应用 ，我们会得到两个内容和大小相同的集合。

由于这两个集合是相同的，所以这两个集合的并集的大小将是相同的，即 。

平方 -th 个单位根产生 -th 个单位根的证明

假设 是 -th 个单位根。我们的目标是证明 是 -th 个单位根，也就是说：

让我们简化 ：

由于 （因为 是 -th 个单位根），所以 。

因此， 的确是 -th 个单位根。

• 原文链接： rareskills.io/post/roots...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～