  This tutorial aims to establish connections between polynomial modular
multiplication over a ring to circular convolution and discrete Fourier
transform (DFT). The main goal is to extend the well-known theory of DFT in
signal processing (SP) to other applications involving polynomials in a ring
such as homomorphic encryption (HE). HE allows any third party to operate on
the encrypted data without decrypting it in advance. Since most HE schemes are
constructed from the ring-learning with errors (R-LWE) problem, efficient
polynomial modular multiplication implementation becomes critical. Any
improvement in the execution of these building blocks would have significant
consequences for the global performance of HE. This lecture note describes
three approaches to implementing long polynomial modular multiplication using
the number theoretic transform (NTT): zero-padded convolution, without
zero-padding, also referred to as negative wrapped convolution (NWC), and
low-complexity NWC (LC-NWC).
