在前一章关于多值函数的图像保持中，我们看到与其在单位根上计算 ，不如将 转换为一个多值函数并在域 上计算它。 展开平方根 将 1 的 8 次方根视为嵌套平方根要容易得多： 现在我们展示如何使用平方根展开来计算： 我们知道 等于 ，因...
NTT（数论变换）算法将有限域中的多项式从系数形式转换为点形式。 如果一个多项式具有 阶数，那么我们在 -th 个单位根上对其进行求值，其中 我们不是在 -th 个单位根的集合 中的每个点上评估多项式 ，而是使用多值函数的像保持定理来评...
范德蒙矩阵 (Vandermonde matrix) 是一个将多项式从其系数表示 (coefficient representation) 转换为其在一组点上的值表示 (value representation) 的矩阵。 对于一个多项式...
偶数的 任何 -th 单位根的 次方将导致 1 或 -1。 这不应与看起来相似的概念混淆，即 或 单位根 和 互为加法逆元。 让我们以本原 8 次单位根为例，生成器（本原 8 次单位根）： 作为给读者的练习，我们建议取 6 次单位根，...
我们将以一个不寻常的提示开始本章 —— NTT 算法非常简单，可以用不到 20 行代码实现。然而，使其工作的关键思想，奇怪的是，没有正式的数学名称。因此，我们将自由地给这个我们认为算法背后的核心定理，起一个（主观上）朗朗上口的名字： 多值...
如果我们取 -th 个单位根的集合（其中 为偶数），并将每个元素平方，结果集合的大小将是原来的一半。新的集合将是 -th 个单位根。 例如，假设 。那么第 6 个单位根是 如果我们把每个元素平方，会得到下面的集合。有些元素的指数大于等于...
一个数字 的平方根 是指满足 的数。当 的形式为 且 为偶数时，平方根很容易计算：它就是 。这遵循指数的幂法则： 如果我们限制指数为整数，那么 有平方根当且仅当 是偶数。因此， 是 的平方根。 平方根有两个解。例如，4 的整数平方根是...
如果 是一个 -th 单位根，那么 和 是加法逆元的性质可能看起来有点抽象——本章介绍了一种可视化方法，使这个概念更容易记住。 回想一下，-th 单位根是通过取本原 -th 单位根 并将其提升到连续幂来生成的。例如，如果 ，我们计算第 4...
区块链技术网
