Abstract
This article presents Flex-NTT, a flexible (configurable) and area-efficient number theoretic transform (NTT) architecture featuring novel unified memory access patterns. The proposed design offers compile-time configurability (CTC) to support various parallel butterfly units (BUs) and run-time configurability (RTC) to accommodate diverse NTT operation sizes without recompilation. A single hardware instance is reconfigurable for NTT, inverse NTT (INTT), and point-wise multiplication, improving hardware utilization. The proposed coefficient and twiddle-factor memory access schemes achieve the theoretical minimum memory sizes, eliminate intermediate buffers, and enable natural-order outputs without additional reordering. FPGA evaluations demonstrate that Flex-NTT achieves up to $4.25 \times $ BRAM savings and $2.82 \times $ performance improvements over prior NTT/INTT designs. When applied to polynomial multiplication, it delivers up to $2.35 \times $ performance and $2.93 \times $ BRAM utilization improvements under the same metric.
Funding Information
  • National Science Foundation