## Chinese Remainder Theorem for Polynomials (Scripts) Publisher's description

from Sundar Krishnan

### 15th July, 2005 : Poly_POWER.m is now corrected !

15th July, 2005 : Poly_POWER.m is now corrected !

So, for most reasonable cases of Multiple Roots including Multiple Real Roots, Poly_POWER.m should now work.

********************

Functional Description of Ch_Rem_Thr_Poly.m :

Assume that we need to find a solution c_soln_Poly

such that it satisfies the foll 4 equations :

Remainder of c_soln_Poly divided by ( 16.x^3 + 5.x^2 + 9.x + 4 ) = 1

Remainder of c_soln_Poly divided by ( 2.x^3 + 11.x^2 + 7.x + 14 ) = 2

Remainder of c_soln_Poly divided by ( 3.x^3 + 10.x^2 + 6.x + 15 ) = 3

Remainder of c_soln_Poly divided by ( 13.x^3 + 8.x^2 + 12.x + 1 ) = 4

The solution c_soln_Poly is :

-0.2561.x^11 -2.1843.x^10 -5.1302.x^9 -4.4053.x^8 ...

-4.0876.x^7 +11.9307.x^6 +23.1045.x^5 +33.0426.x^4 ...

+36.8186.x^3 +20.7266.x^2 +13.9833.x +5.0903

Now, how did we find this c_soln_Poly ?

The answer is this Programme, the application of the Chinese Remainder

Theorem for Polynomials.

The above problem can be stated in a more mathematical language as :

c_soln_Poly =eqvt mod ( 1, { Poly with coeffs : [16 5 9 4] } )

c_soln_Poly =eqvt mod ( 2, { Poly with coeffs : [ 2 11 7 14] } )

c_soln_Poly =eqvt mod ( 3, { Poly with coeffs : [ 3 10 6 15] } )

c_soln_Poly =eqvt mod ( 4, { Poly with coeffs : [13 8 12 1] } )

where "=eqvt" implies "congruence" with the usual symbol of 3 equal-to lines.

The Poly coeffs used above are nothing but columns of magic(4)

ie, we have made Polynomials out of the column-wise coeffs of magic(4).

mk_Poly = magic(4) ;

That the Remainders are resp 1, 2, 3 and 4 wrt the 4 Polys of magic(4)

can be verified by :

[QT, RT] = deconv ( c_soln_Poly, mk_Poly (:, 1) ) ; % RT = 1

[QT, RT] = deconv ( c_soln_Poly, mk_Poly (:, 2) ) ; % RT = 2

[QT, RT] = deconv ( c_soln_Poly, mk_Poly (:, 3) ) ; % RT = 3

[QT, RT] = deconv ( c_soln_Poly, mk_Poly (:, 4) ) ; % RT = 4

The Chinese Remainder Theorem for Polynomials is defined in

still more mathematical notations in literature as follows

(for eg, in the book by Richard Blahut / P77) :

For any set of Pair-wise Coprime Polynomials [m1(x), m2(x), ... mk(x)],

the set of congruences :

c(x) =eqvt mod ( ck(x), mk(x) ), k = 1, 2, ... k

has a unique solution of a degree less than the degree

of M(x) = prod (m1(x), m2(x), ... mk(x)), given by :

c_soln_Poly(x) = sum ( mod ( ck(x).Nk(x).Mk(x), M(x) ) )

where Mk(x) = M(x) / mk(x), and Nk(x) is the Polynomial that satisfies

Nk(x).Mk(x) + nk(x).mk(x) = GCD = 1

(this is where we need to use my programmes Poly_GCD.m and Poly_GCD_Main.m)

I understood these notations better only after / when I read P 21

of the book by Neal Koblitz describing the Chinese Remainder Theorem

for Integers. Blahut also describes the Chinese Remainder Theorem

for Integers in P 70.

Please also refer to my programme Ch_Rem_Thr_Int.m for Integers.

This programme for Polynomials is developed partly based on similar concepts.

One of the most important prerequisites for this Theorem and

the programme, is that the Column-wise Polys of input mk_Poly

be Pair-wise Coprime. So, we first check if all the k*(k-1)/2

This programme makes heavy usage of the other programme Poly_GCD.m,

and hence, is also subject to the same constraints and limitations,

only these limitations are still more stringent here.

I have so far observed only 2 Non-convergent cases :

Poly 2 of magic(8), Poly 4 of magic(7)

These two cases can be good test cases for any future

changes in the empirical logics of this programme.

It will be highly desirable to find a logic that will give GCD = 1

for these cases.

Should also generally work for R13 and R12 (but Poly_POWER cannot work only in R12).

#### System Requirements:

MATLAB 7 (R14)**Program Release Status:**New Release

**Program Install Support:**Install and Uninstall