NTT

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

本文介绍了ICICLE V1.6.0版本的一系列更新，包括稳定的Golang绑定、多GPU支持、向量运算API、Grumpkin曲线支持、NTT改进和MSM改进。这些更新旨在提升零知识证明（ZKP）加速的性能和效率，并扩展ICICLE的应用范围，如支持更大的电路和更多编程语言。

本文介绍了ICICLE库的更新，该库使用CUDA加速GPU上的ZK证明。主要更新包括：支持Poseidon哈希和优化的Merkle树构建器，新的混合基数NTT算法，改进的MSM设计，以及修复了Rust绑定在Windows上的支持问题。还包括性能测试结果，展示了Poseidon哈希树构建器和NTT算法的性能提升。

本文介绍了对 rapidsnark 进行 GPU 加速的动机、背景和性能。通过将硬件加速集成到 rapidsnark 中，性能达到了 CPU 版本的约 4 倍。主要针对 NTT 和 MSM 计算进行优化，Orbiter Finance 团队开源了加速后的 rapidsnark 代码。

本文探讨了利用 WebGPU 加速客户端零知识证明（ZKP）的方法。WebGPU 是一种可以在多种平台（包括移动设备）上利用 GPU 的技术，通过并行计算和优化内存使用，能够显著提升证明速度。文章详细介绍了 WebGPU 的基本原理、内存层级结构，以及在 WGSL 中实现 NTT（数论变换）的优化过程，最后讨论了将 WebGPU 集成到 ZK 框架中的挑战和未来方向。

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

本文深入探讨了多项式乘法的优化方法，首先回顾了传统的多项式乘法，然后研究了多项式的不同表示形式（系数形式和点值形式），接着比较了在这些形式下的多项式算术，最后讨论了如何利用这些形式加速多项式乘法，并引出了数论变换（NTT）算法。文章详细解释了系数形式和点值形式之间的转换，并分析了优化转换过程以实现更快多项式乘法的策略。

本文深入探讨了多项式乘法，特别是在零知识证明和密码学中的应用。文章首先回顾了传统的多项式乘法方法，然后研究了多项式的不同表示形式（系数形式和点值形式），比较了在不同形式下的多项式算术，并探讨了如何利用这些形式加速多项式乘法，最终引出了数论变换(NTT)算法。NTT通过在\(\mathcal{O}(n \log n)\)时间内进行求值和插值，从而加速多项式乘法。

对比不同的可跨链 Token 框架： ITS 、 NTT 、 OFT 、 Warp Token 、xERC20

ICICLE 是一个使用 CUDA-enabled GPUs 进行 ZK 加速的库。最新版本引入了 ECNTT、列式 NTT 处理、MSM 预计算等新特性，并优化了编译时间。即将发布的 v2 版本将提供丰富的多项式 API，并支持在 GPU 内部运行端到端的证明器。

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

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

本文介绍了数论变换（NTT）算法，该算法用于将有限域中的多项式从系数形式转换为点值形式。文章通过使用平方根展开，并结合像保留定理，优化了在单位根上评估多项式的过程，并给出了在四次和八次单位根上评估多项式的示例，展示了NTT算法的计算过程和优化方法。