7.2.1 数论变换 (NTT)：加速多项式乘法

文档摘要

7.2.1 数论变换 (NTT)：加速多项式乘法在高性能密码学、同态加密、快速傅里叶变换（FFT）替代方案以及大规模多项式运算的工程实践中，有一个常被低估却极具锋芒的工具——数论变换（Number Theoretic Transform, NTT）。它不像FFT那样家喻户晓，却在整数域上构筑起一座无需浮点误差、无须内存对齐、可完全确定性验证的高速多项式乘法桥梁。当你在实现BFV或CKKS方案时卡在多项式乘法的吞吐瓶颈；当你调试一段NTT代码发现结果总差一个模数倍数却找不到根源；当你反复调整、、却仍无法让逆变换完美还原原系数——这不是数学错了，而是工程细节在低语：“你还没真正把它焊进系统里。” 本节不讲NTT的群论起源，不复述DFT类比，也不堆砌抽象定理。