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 c*_{i} = *R*_{mi}[*c*], *for i* = 0, 1, · · · , *k*, where *m*_{i} *are moduli and are relatively prime, then*

*where M* = *m _{i}*,

*provided that* 0 ≤ *c* < *M. The notation* *R*_{mi}[*c*] *represents the remainder when c is divided by m_{i}*.

**Theorem 8.3.2 CRT for Polynomials**

*Given c*^{(i)}(*p*) = *R*_{m(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*

Start Free Trial

No credit card required