Download Shareware and Freeware Software for Windows, Linux, Macintosh, PDA

line Home  |  About Us  |  Link To Us  |  FAQ  |  Contact

Serving Software Downloads in 976 Categories, Downloaded 31.570.333 Times

Chinese Remainder Theorem for Polynomials 1.0

  Date Added: June 01, 2013  |  Visits: 203

Chinese Remainder Theorem for Polynomials

Report Broken Link
Printer Friendly Version

Product Homepage
Download (19 downloads)

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

License: Shareware Size: 112.64 KB
Development Tools  -  A Benchmark Problem for Model Based Control System Tests - 001 1.0
Today safety critical flight control systems are tested using model based approach. The model blocks are proprietary and seldom shared in the open. A benchmark problem was designed as part of a research activity to test out certain test case...
3.33 MB  
Development Tools  -  Converts between decimal integers to multiple based numbers 1.0
DEC2MBASE: converts decimal integers to multiple based numbers.MBASE2DEC: the inverse function of DEC2MBASE.Two corresponding html documents are also supplied for detailed documentation.
10 KB  
Development Tools  -  Euler_Phi and Its Applications 1.0 is a suite of the foll Programmes :1) Euler_Phi (n) returns the no of positive integers less than n which are prime to n.2) a_k_mod_m_LCM_Method (a, m, k) : Imagine computing mod(14^26, 45) or mod(56^3005, 1125).This programme...
10 KB  
Utilities  -  Source Mage GNU/Linux
Source Mage GNU/Linux distribution is based on a sorcerous metaphor of "casting" and "dispelling" packages, which we refer to as "spells". This is a development ISO and potentially loaded with bugs and glitches. This is where you come in. We...
247 MB  
Utilities  -  Source Mage GNU/Linux 0.9.6 PPC
Source Mage GNU/Linux distribution is based on a sorcerous metaphor of "casting" and "dispelling" packages, which we refer to as "spells". This is a development ISO and potentially loaded with bugs and glitches. This is where you come in. We...
207.9 MB  
Utilities  -  phpXIedit 0_7_beta
phpXIedit is a web based application to edit, validate and preview XML documents. This document describes the installation and basic functionality of phpXIedit. The package can be downloaded at
409.6 KB  
Development Tools  -  Digital Control System Analysis and Design, 3e 1.0
Designed for a senior-level course in digital or discrete-time controls, this third edition has been updated to include MATLAB based examples for problem solving.For a full book description and ordering information, please refer to...
61.44 KB  
Development Tools  -  Using MathWorks Tools to Apply Model-Based Design for DO-178B Applications 1.0
This example demonstrates the use of The MathWorks product family to apply Model-Based Design in the development of applications that may be certified using DO-178B or ARP-4754 standards.This example will step through the complete software...
2.56 MB  
Development Tools  -  MATLAB Contest Paper 1.0
This paper describes the web-based MATLAB programming contests and points out some interesting connections between the contests and opensource software development.[This paper was presented at CHI 2001.]
102.4 KB  
Development Tools  -  Differential Evolution Based Channel and Feature Selection 1.0
One of the fundamental motivations for feature selection is to overcome the curse of dimensionality problem. This code presents a novel feature selection method utilizing a combination of differential evolution (DE) optimization method and a...
10 KB  
Scripts  -  Freelancer Script 5.05
Main Features: 100% Secured. Email Support (3 Years). FREE Updates (3 Years). Post projects. Featured projects. Private projects. Sealed projects. Edit/delete projects. Select freelancers....
5.49 MB  
Scripts  -  B2B Script 4.20
Main Features: 100% Secured. Email Support (3 Years). FREE Updates (3 Years). Sign-up Account (Registration of account). Lead generation tools (for the sellers). Email verification to...
5.49 MB  
Scripts  -  B2C Script 5.06
Main Features: 100% Secured. Email Support (3 Years). FREE Updates (3 Years). The script comes with totally editable site colors, icons and graphics Multilevel categories allows extensive browsing Admin can change Category ordering or...
5.49 MB  
Scripts  -  Social Networking Script 2.86
Main Features: 100% Secured. Email Support (3 Years). FREE Updates (3 Years). Registration with name, email, password, date of birth etc. User can add multiple school, college, university with start...
5.49 MB  
Scripts  -  Business Networking Script 8.04
Main Features: 100% Secured. Email Support (3 Years). FREE Updates (3 Years). Ajax based interface. Profile creation. Different types of profile. Profile for jobseekers, employers and employed...
5.49 MB  
Development Tools  -  VMP Viewer 1.0
This is a very rudimentary tool to visualize the VMP files generated by BrainVoyager. Useful to share files with people who do not have BV.
10 KB  
Development Tools  -  Sending reports and timestamped file by emailing 1.0
main executing reference usage:[1] usage_send_mail.mIllustrates email sending with multiple separate files or single timestamped tar file. Attachment failure is properly handled, with continuation of report emailing without the attachment.[2]...
768 KB  
Development Tools  -  IrisMVC 2.0 rc1
IrisMVC is an OOP PHP framework that developers can use as a strong and secure foundation to build on various web applications following the Model-View-Controller (MVC) pattern. It provides the basic functionality developers need, without...
51.2 KB  
Development Tools  -  7-Zip for Script 4.42
7-Zip is a file archiver with a high compression ratio.Features:- High compression ratio in new 7z format with LZMA compression- Supported formats:- Packing / unpacking: 7z, ZIP, GZIP, BZIP2 and TAR- Unpacking only: RAR, CAB, ISO, ARJ, LZH, CHM,...
624.64 KB  
Development Tools  -  Barnardextest 1.0
This file, as the Fisher's exact test, performs the exact probability test for a table of frequency data cross-classified according to two categorical variables, each of which has two levels or subcategories (2x2). It is a non-parametric...
10 KB