Number theoretic transform based on ternary arithmetic

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 new NTT is then described and is compared with the implementation of conventional NTT´s based on binary modular arithmetic.