Revisiting Fast Fourier multiplication algorithms on quotient rings

04/18/2023

∙

by   Ramiro Martínez, et al.

∙

0

∙

share

This work formalizes efficient Fast Fourier-based multiplication algorithms for polynomials in quotient rings such as ℤ_m[x]/<x^n-a>, with n a power of 2 and m a non necessarily prime integer. We also present a meticulous study on the necessary and/or sufficient conditions required for the applicability of these multiplication algorithms. This paper allows us to unify the different approaches to the problem of efficiently computing the product of two polynomials in these quotient rings.