Multivariate polynomial products over modular rings using residue arithmetic

A computational system called the polynomial residue number system (PRNS) has previously been proposed and analyzed. It solves the problem of multiplying two univariate polynomials modulo (x^N±1) over the modular ring Z_p. In the present paper, extensions of PRNS for computing the product of two multivariate polynomials modulo a polynomial are developed. Such a number system is termed as multivariate polynomial residue number system (MPRNS). MPRNS is essentially an isomorphic representation between the ring Z_p[x]/Π_i=1^L (x_i(N _i)±1) of L-variate polynomials in the indeterminate vector x=(x₁, x₂, …, x_L) and the ring Z_p(N₁N₂…N_L). Issues related to existence of isomorphic mappings, their properties and multiplicative complexity of the resulting algorithm have been addressed. The applications of the MPRNS scheme are also presented