Intro to Analysis of Algorithm
Intro to Analysis of Algorithm CSCI 350
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 5 page Class Notes was uploaded by Laurianne Mante on Saturday October 3, 2015. The Class Notes belongs to CSCI 350 at Bucknell University taught by Stephen Guattery in Fall. Since its upload, it has received 27 views. For similar materials see /class/218090/csci-350-bucknell-university in ComputerScienence at Bucknell University.
Reviews for Intro to Analysis of Algorithm
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/03/15
CSC1350 Spring 2006 Slide Set 18 The Chinese Remainder Theorem The Chinese Remainder Theorem 0 Theorem 3127 see text pp 873874 Let n 141142 nk where the Hi are pairwise relatively prime Consider the correspondence a lt gt a1 a2 a where a 6 Zn a1 6 Zni and a1 a mod ni for i 1 2 k The correspondence above is a onetoone correspondence bijection between Zn and the Cartesian product anx ZnZXgtlt an Uses of the Chinese Remainder Theorem 0 It shows that the structure of Zn is identical to that of anx anxgtlt an using the operations de ned in the text 0 Using the Cartesian product representation may give ef cient algorithms in terms of the number of bitwise operations required for arithmetic operations Additional Results 0 Corollary 3128 If n1 n2 nk are pairwise relatively prime and n 141142 nk then for any integers a a2 ak the set of simultaneous equations x E at mod ml for i 1 2 khas a unique solution modulo n for the unknown x Additional Results 2 0 Corollary 3129 If n1 n2 nk are pairwise relatively prime and n 171142 nk then for all integers x and a x E a mod ni fori l 2 kifand only if x E a mod n