Publisher review:Chinese Remainder Theorem for Polynomials verifies the Chinese Remainder Theorem for Polynomials (of "congruence") 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 ) = 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.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 = 4The 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, ... 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 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)/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 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) Requirements: ยท MATLAB Release: R14
Chinese Remainder Theorem for Polynomials is a Matlab script for Mathematics scripts design by Sundar Krishnan.
It runs on following operating system: Windows / Linux / Mac OS / BSD / Solaris.
Operating system:Windows / Linux / Mac OS / BSD / Solaris
Chinese Remainder Theorem for Polynomials script details 
