Improved Polynomial Multiplication Formulas over $IF₂$ Using Chinese Remainder Theorem

Let n and lscr be positive integers and f(x) be an irreducible polynomial over IF₂ such that lscrdeg(f(x)) < 2n -1. We obtain an effective upper bound for the multiplication complexity of n-term polynomials modulo f(x)^lscr. This upper bound allows a better selection of the moduli when Chinese Remainder Theorem is used for polynomial multiplication over IF₂. We give improved formulae to multiply polynomials of small degree over IF₂. In particular we improve the best known multiplication complexities over IF₂ in the literature in some cases.