Area-Efficient Modular Reduction Structure and Memory Access Scheme for NTT

Number theoretic transform based multiplication is commonly used in Post-quantum cryptography, which is the most resource-consuming operation. In this paper, we propose an area-efficient modular reduction structure for generalized Mersenne primes with interval prediction, and a novel memory access scheme which fetches two data at the same side of a butterfly unit simultaneously. By the interval prediction structure, some adders are eliminated in a modular multiplication. When implement it in 3-stage pipeline mode and synthesize it with TSMC 90nm process, this structure achieves approximate 14.9% less area compared with other designs. The proposed memory access scheme is an in-place scheme. It is more regular than other designs and the two pieces of memory share the same address. Based on this characteristic, we construct an address generator which consumes 40% less area.