Using Python programming language implement the Chinese Remainder Theorem.

Specifications: The program should take the following inputs:

1) A positive semi-prime integer n, which is the modulus

2) Two prime numbers p and q that are the prime factors of n. The program should then construct, store and output the table of residues modulo (p,q) for all the integers in Zn. Next, the program should prompt the user to specify one of three arithmetic operations i.e. +, - and x and two integers value a and b in Zn The program should then lookup the residue values for a and b, and output them to the screen. It should then use the residue values to calculate the result of the specified arithmetic operation e.g. (a + b) mod n, if the addition operation was specified. The program should output the result of the operation and the residue values of the result. It should them prompt the user for another set of numbers or an option for the program to exit.

Question

1) What data structure did you use to implement your residue table? What is the computational complexity of looking up values in your residue table?

Test

t1) Run your program with n = 115 p = 23 q = 5

2) Provide a screenshot of the constructed residue table

3) Run your program three times, each time using one of addition, subtraction and multiplication respectively. For each operation chose random values of a and b in Z115

4) Provide screenshots of the results

5)Exit from your program