# Chinese Remainder Theorem for Polynomials 1.0

OS : Windows / Linux / Mac OS / BSD / Solaris

Script Licensing : Freeware

Created : Aug 30, 2007

Downloads : 2

Thank you for voting...

## Functional Description of Ch_Rem_Thr_Poly.m :<br ...

Functional Description of Ch_Rem_Thr_Poly.

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

-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 by Sundar Krishnan.

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)

[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 1.0 is defined in still more mathematical notations in literature as follows (for eg,

has a unique solution of a degree less than the degree

of M(x) = prod (m1(x), m2(x), . . . mk(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)

**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 ) = 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 by Sundar Krishnan.

**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 1.0 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 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)

**• MATLAB Release: R14**

**Demands:****Chinese Remainder Theorem for Polynomials 1.0 scripting tags:**chinese, mod, theorem, remainder, matlab mathematics, eqvt, coeffs, csolnpoly, chinese remainder, theorem polynomials.

**What is new in Chinese Remainder Theorem for Polynomials 1.0 software script?**- Unable to find Chinese Remainder Theorem for Polynomials 1.0 news.

**What is improvements are expecting?**Newly-made Chinese Remainder Theorem for Polynomials 1.1 will be downloaded from here. You may download directly. Please write the reviews of the Chinese Remainder Theorem for Polynomials. License limitations are unspecified.