## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required