Skip to main content
Engineering LibreTexts

3.2: Polynomial Reduction and the Chinese Remainder Theorem

  • Page ID
    1973
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Residue reduction of one polynomial modulo another is defined similarly to residue reduction for integers. A polynomial \(F(s)\) has a residue polynomial \(R(s)\) modulo \(P(s)\) if, for a given \(F(s)\) and \(P(s)\), a \(Q(s)\) and \(R(s)\) exist such that:

    \[F(s)=Q(s)P(s)+R(s) \nonumber \]

    with

    \[degree{R(s)}<degree{P(s)} \nonumber \]

    The notation that will be used is:

    \[R(s)=((F(s)))_{P(s)} \nonumber \]

    For example,

    \[(s+1)=((s^{4}+s^{3}-s-1))_{(s^{2}-1)} \nonumber \]

    The concepts of factoring a polynomial and of primeness are an extension of these ideas for integers. For a given allowed set of coefficients (values of \(x(n)\)), any polynomial has a unique factored representation:

    \[F(s)=\prod_{i=1}^{M}F_{i}(s)^{k_{i}} \nonumber \]

    where the \(F_i(s)\) are relatively prime. This is analogous to the fundamental theorem of arithmetic.

    There is a very useful operation that is an extension of the integer Chinese Remainder Theorem (CRT) which says that if the modulus polynomial can be factored into relatively prime factors:

    \[P(s)=P_{1}(s)P_{2}(s) \nonumber \]

    then there exist two polynomials, \(K_1(s)\) and \(K_2(s)\), such that any polynomial \(F(s)\) can be recovered from its residues by:

    \[F(s)=K_{1}(s)F_{1}(s)+K_{2}(s)F_{2}(s)\: mod\: P(s) \nonumber \]

    where \(F_1\) and \(F_2\) are the residues given by:

    \[F_{1}(s)=((F(s)))_{P_{1}(s)} \nonumber \]

    and

    \[F_{2}(s)=((F(s)))_{P_{2}(s)} \nonumber \]

    if the order of \(F(s)\) is less than \(P(s)\). This generalizes to any number of relatively prime factors of \(P(s)\) and can be viewed as a means of representing \(F(s)\) by several lower degree polynomials, \(F_i(s)\).

    This decomposition of \(F(s)\) into lower degree polynomials is the process used to break a DFT or convolution into several simple problems which are solved and then recombined using the CRT of the above equation. This is another form of the “divide and conquer" or “organize and share" approach similar to the index mappings in Multidimensional Index Mapping.

    One useful property of the CRT is for convolution. If cyclic convolution of \(x(n)\) and \(x(n)\) is expressed in terms of polynomials by:

    \[Y(s)=H(s)X(s)\: mod\: P(s) \nonumber \]

    where

    \[P(s)=s^{N}-1 \nonumber \]

    and if \(P(s)\) is factored into two relatively prime factors

    P=P1P2P=P1P2" role="presentation" style="position:relative;" tabindex="0">


    This page titled 3.2: Polynomial Reduction and the Chinese Remainder Theorem is shared under a CC BY license and was authored, remixed, and/or curated by C. Sidney Burrus.

    • Was this article helpful?