# using any programming language of your choice implement the chinese remainder theorem

1) Using any programming language of your choice implement the Chinese Remainder
ensure that you use a programming language that is compatible with IRIS and
also ensure the program can run on IRIS before submitting it
2) 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
1) 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
Submission
Submit the following documents separately in Blackboard by the deadline. NO ZIPPED
FILES ALLOWED
2) A detailed README file, which should explain how to run the code with sample
input and output. If you are unfamiliar with READMEs you can find an
7ac01da88ab3 and here
Note that the README file you
submit for this project need not be complex, it only needs to at least explain how
to compile the code and run the code with examples.
3) A MAKEFILE that automates the building/compiling of your code. If you are
unfamiliar with Makefiles you can get a quick introduction here
and here
https://swcarpentry.github.io/make-novice/02-makefiles/. Note that the exact
structure of your makefile will depend on the programming language you are
using, so you may choose to find an example specific to you. The Makefile you
create for this assignment need not be complicated. It only needs to define the
TARGET, its DEPENDENCIES, if any and the COMMAND to create the target
executable.