Algorithmic Views of Vectorized Polynomial Multipliers – NTRU Prime

ePrint Report: Algorithmic Views of Vectorized Polynomial Multipliers – NTRU Prime

Vincent Hwang, Chi-Ting Liu, Bo-Yin Yang

In this paper, we explore the cost of vectorization for polynomial multiplication with coefficients in Zq for an odd prime q. If there is a large power of two dividing q−1, we can apply radix-2 Cooley–Tukey fast Fourier transforms to multiply polynomials in Zq[x]. The radix-2 nature admits efficient vectorization. Conversely, if 2 is the only power of two dividing q−1, we can …

cost eprint report large ntru prime power prime report