单位根

本文深入探讨了全同态加密（FHE）中的单指令多数据（SIMD）操作，详细阐述了如何利用代数和数论的概念，特别是理想、商环、单位根、分圆多项式以及中国剩余定理，将多个明文值打包进一个密文中，并同时进行并行计算，从而显著提高FHE的效率，使其从理论走向实际应用。文章还探讨了如何通过Galois自同构和掩码技术实现数据的移动和旋转。

文章深入探讨了快速傅里叶变换（FFT）的数学原理及其在零知识证明（ZK）协议中的核心地位。作者详细解释了如何利用单位根的对称性与平方封闭性，通过分治递归将多项式在系数表示与点值表示之间的转换复杂度从 O(n²) 降低至 O(n log n)，为现代高效 ZK 证明系统提供了理论支撑。

本文深入探讨了单位根的正交性（Orthogonality of Roots of Unity），这是数论变换（NTT）的核心数学基础。文章通过有限域 F17 的具体示例，证明了由本原 k 次单位根生成的幂次和规律：当幂次不是 k 的倍数时，其和为 0；当幂次是 k 的倍数时，其和为 k。作者利用几何级数公式给出了严谨的数学证明，并将其推广到两个单位根向量的内积形式。这一性质在信号处理和零知识证明的快速傅里叶变换中至关重要，是理解多项式乘法加速的关键。

本文证明了一个关键性质：对于由本原k次单位根ω生成的范德蒙德矩阵V(ω)，其逆矩阵是1/k乘以另一个范德蒙德矩阵V(ω⁻¹)。通过两种方式证明：1) 直接矩阵乘法，利用单位根的正交性得到单位矩阵；2) 通过系数向量与多项式求值的变换，验证两次变换后恢复原系数。该性质是数论变换（NTT）逆变换的基础。

本文介绍了有限域中的单位根的概念以及它们与乘法子群的关系。文章证明了在有限域中，当 k 能整除 p-1 时，k 次单位根的集合与 k 阶乘法子群相同。同时，文章还解释了如何找到本原单位根，并提供了一些例子来展示如何使用基本定理来寻找给定 k 的所有 k 次单位根。

本文介绍了图像保持定理，它是数论变换（NTT）的核心概念。该定理指出，对于多值函数，在特定条件下的图像与原始函数在不同定义域上的图像相同。通过重复取平方根来计算单位根，并展示了如何利用该定理来优化多项式求值，为后续章节中利用平方根扩展评估多值函数奠定基础。

本文介绍了在有限域中执行FFT算法（数论变换）所需的n次单位根，并列举了几个常用的FFT友好的有限域，包括Goldilocks Field、Baby Bear Field、Teddy Bear Field、Koala Bear Field、BN-128 field、STARK Field和BLS12-381，以及它们各自的特征和单位根的阶数，并提供了相应的Python代码验证。

本文深入探讨了ZK-STARKs中约束的执行以及如何处理周期性应用的约束。文章解释了如何将计算的执行轨迹转换为多项式，并利用单位根的性质来简洁地表达和验证约束，尤其是在约束条件周期性重复出现的情况下，从而优化性能并简化理解。

本文介绍了数学群在零知识证明和密码学中的基础作用。它详细阐述了群的定义、特性，并深入探讨了整数模p乘法群和椭圆曲线群。文章还涵盖了循环群、生成元、离散对数问题以及单位根等关键概念，强调了它们在现代密码系统和零知识技术中的重要性。

本文是《零知识书》中关于逆数论变换（INTT）的章节，详细解释了如何将多项式从点值形式（单位根上的求值）转换回系数形式（插值）。通过Vandermonde矩阵和其逆矩阵的乘法进行推导，以四次单位根为例，验证了逆矩阵的正确性，并推广到一般k次单位根的情形。

本文通过可视化方法，利用单位圆解释了 n 次单位根的性质，特别是当两个单位根的指数相差 n/2 时，它们互为加法逆元。文章通过图示和动画生动地展示了单位根的乘法和加法运算在单位圆上的几何意义，并解释了如何在单位圆上可视化同余关系。

当对偶数阶的单位根集合中的每个元素进行平方时，得到的新集合大小是原来的一半。文章通过举例和证明，详细解释了这一现象，并说明了为什么k必须是偶数，同时证明了平方一个k次单位根会产生一个 k/2 次单位根。

本文介绍了在指数形式下求平方根的方法，特别是在单位根上的应用。文章解释了只有偶数次幂的单位根才能开平方，并展示了如何通过开平方操作将k次单位根转化为2k次单位根，同时提供了相关的示例和练习题。

本文介绍了使用平方根展开方法在单位根上评估多值函数。通过将函数转换为多值函数并在域上进行评估，避免了直接在单位根上进行评估的复杂性。文章详细展示了如何通过嵌套平方根来展开和简化计算，并探讨了不同类型的项（如 和 ）的计算复杂性，以及如何优化多项式以减少计算量，最终引出快速数论变换（NTT）算法。

本文讨论了将k次单位根 ω 提高到 k/2 次方的问题，结果只能是1或-1。文章给出了证明，当指数为偶数时，结果为1；当指数为奇数时，结果为-1。这种性质可以用于优化多项式在单位根上的求值计算，通过因式分解尽可能多地提取出 x^(k/2) 项，从而简化计算。