Number theoretic transform based on ternary arithmetic and its application to cyclic convolution

A number theoretic transform (NTT) is proposed, which can efficiently be computed by using ternary modular arithmetic. The new NTT relaxes the restriction imposed on the convolution length and, as in other efficient NTT's, its computation can be performed by means of data shifts and additions. A hardware implementation of the cyclic convolution using the proposed NTT is then described.