一种基于常量几何结构的NTT（Number Theoretic Transform）的多项式乘法器，经过内存优化设计，并采用了无冲突的位反转重排序方法

《IEEE Transactions on Very Large Scale Integration (VLSI) Systems》：A Memory-Optimized Constant Geometry NTT-Based Polynomial Multiplier With a Conflict-Free Bit-Reverse Reordering Method

　　

摘要：

数论变换（NTT）及其逆变换（INTT）常被用于加速多项式乘法运算，而多项式乘法既是基于格的密码学（LBC）中的核心计算范式，也是性能瓶颈。作为NTT算法家族中的一个重要变体，常数几何（CG）NTT因其简单且一致的内存访问模式而受到了许多研究人员的关注。然而，它存在两个固有的、令人不满的局限性：首先，它对多项式系数的存储容量要求较高，这会超出某些系统的限制；其次，在NTT和INTT之间进行数据读写时不可避免地需要重新分配内存，从而导致冲突。为了解决这些问题，本文提出了一种改进的“乒乓球”内存结构，并采用了一种新的无冲突位反转排序方法。在改进的“乒乓球”内存结构中，每个处理单元（PE）仅分配两个内存银行，从而将总体存储需求降低到了较低的水平。此外，所提出的位反转排序算法通过简单的逻辑和低资源开销，有效避免了读写冲突，并实现了内存中的无缝数据重新分配，而不会导致系统停滞或占用额外空间。我们还引入了一种轻量级的“twiddle因子”内存访问方案，结合上述技术，进一步降低了控制逻辑和内存的资源消耗。最后，所提出架构的FPGA实现结果表明，在面积效率方面相比现有方案具有显著的优势。