The Winograd short convolution algorithm is based on the CRT over an integer ring, which can be stated as:
“It is possible to uniquely determine a nonnegative integer given only its remainders with respect to the given moduli, provided that the moduli are relatively prime and the integer is known to be smaller than the product of the moduli.”
In a polynomial ring over any field, there again exists a CRT. Both the CRT over an integer ring and the CRT over a polynomial ring are summarized below.
Theorem 8.3.1 CRT for Integers
Given ci = Rmi[c], for i = 0, 1, · · · , k, where mi are moduli and are relatively prime, then
where M = mi, Mi = M/mi and Ni is the solution of
provided that 0 ≤ c < M. The notation Rmi[c] represents the remainder when c is divided by mi.
Theorem 8.3.2 CRT for Polynomials
Given c(i)(p) = Rm(i)(p)[c(p)], for i = 0, 1, · · · , k, where m(i)(p) are relatively prime, then
where and N(i)(p) is the solution of
provided that the degree of c