GF(pm) multiplication using polynomial residue number systems

GF(p^m) multiplication is computed in two stages. First, the polynomial product is computed modulus: a highly factorizable degree S polynomial, M(x), with S⩾2·m-1. This enables the product to be computed using a polynomial residue number system (PRNS). Second, the result is reduced by the irreducible polynomial, I(x), over which GF(p ^m) is defined. Suitable choices for S, M(x) and I(x) are discussed and an iterative method for the factorization of x^T-k polynomials, k ε GF(p), is presented. Finally, multidimensional PRNS is proposed to solve the upper limit constraint on m, which is dependent on p