Chinese Remainder Theorem for Polynomials 1.0

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_Polysuch that it satisfies the foll 4 equations :Remainder of c_soln_Poly divided by ( 16.x^3 + 5.x^2 + 9.x + 4 ) = 1Remainder of c_soln_Poly divided by ( 2.x^3 + 11.x^2 + 7.x + 14 ) = 2Remainder of c_soln_Poly divided by ( 3.x^3 + 10.x^2 + 6.x + 15 ) = 3Remainder of c_soln_Poly divided by ( 13.x^3 + 8.x^2 + 12.x + 1 ) = 4The 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.0903Now, how did we find this c_soln_Poly ?The answer is this Programme, the application of the Chinese RemainderTheorem 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 = 4The Chinese Remainder Theorem for Polynomials is defined instill 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, ... khas a unique solution of a degree less than the degreeof 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 satisfiesNk(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 21of the book by Neal Koblitz describing the Chinese Remainder Theoremfor Integers. Blahut also describes the Chinese Remainder Theoremfor 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 andthe programme, is that the Column-wise Polys of input mk_Polybe Pair-wise Coprime. So, we first check if all the k*(k-1)/2This 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 futurechanges in the empirical logics of this programme.It will be highly desirable to find a logic that will give GCD = 1for these cases.Should also generally work for R13 and R12 (but Poly_POWER cannot work only in R12).

Requirements:	No special requirements
Platforms:	Matlab
Keyword:	Based,  Describes,  Describing,  Integers,  Koblitz,  Refer
Users rating:	0/10