2023/04/18 by Ramiro Martínez, Martínez, Ramiro, Paz Morillo +1
Computer Science · Mathematics · #13B25 (Secondary) #65T50 (Primary) 68W99 #Coding theory and cryptography #Commutative Algebra and Its Applications #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2304.08860
openalex publication_date 2023/04/18 · openalex created_date 2023/04/22 · openalex updated_date 2026/08/04
This work formalizes efficient Fast Fourier-based multiplication algorithms for polynomials in quotient rings such as ℤm[x]/, 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.