1. (a) We will say that two positive integers, ni and nj, are relatively prime if...

  

Transcribed Image Text:

1. (a) We will say that two positive integers, ni and nj, are relatively prime if the greatest common divisor of n, and nj is 1. Suppose that we are given a system of equations: x = a mod n x = a2 mod n x = am mod nm where each n, and n, are relatively prime for ij. For N = I1 ni, give an efficient algorithm to compute a solution to this system of equations x that is between 0 and N - 1. (Note: by "efficient algorithm," we mean one that runs in time that is asymptotically bounded by a polynomial function of the total number of digits appearing in n1, n2,..., nm. Here and everywhere else in the course, this means that you should (i) show that your algorithm is correct and (ii) show that it always finishes in such a bounded amount of time.) (b) Show that a {0,1,..., N - 1} is uniquely determined by a {0,1,...,n -1}, a2 {0, 1,...,n2 - 1},..., am {0, 1,...,nm - 1} and vice versa. That is that for each such system of equations there is a unique solution, and for each such x (and fixed n, n2,..., nm) there is a unique system of equations for which is a solution. 1. (a) We will say that two positive integers, ni and nj, are relatively prime if the greatest common divisor of n, and nj is 1. Suppose that we are given a system of equations: x = a mod n x = a2 mod n x = am mod nm where each n, and n, are relatively prime for ij. For N = I1 ni, give an efficient algorithm to compute a solution to this system of equations x that is between 0 and N - 1. (Note: by "efficient algorithm," we mean one that runs in time that is asymptotically bounded by a polynomial function of the total number of digits appearing in n1, n2,..., nm. Here and everywhere else in the course, this means that you should (i) show that your algorithm is correct and (ii) show that it always finishes in such a bounded amount of time.) (b) Show that a {0,1,..., N - 1} is uniquely determined by a {0,1,...,n -1}, a2 {0, 1,...,n2 - 1},..., am {0, 1,...,nm - 1} and vice versa. That is that for each such system of equations there is a unique solution, and for each such x (and fixed n, n2,..., nm) there is a unique system of equations for which is a solution.

Answer rating: 100% (QA)

This problem statement is referring to a situation that can be efficiently resolved using the Chinese Remainder Theorem CRT The CRT asserts that if on... View the full answer