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

1) Using any programming language of your choice implement the Chinese Remainder

Theorem. Please note that your submission is expected to run on IRIS. Please

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

5)Exit from your program

Submission

Submit the following documents separately in Blackboard by the deadline. NO ZIPPED

FILES ALLOWED

1) All your code files

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

introduction here https://www.makeareadme.com/ , here

https://medium.com/@meakaakka/a-beginners-guide-to-writing-a-kickassreadme-

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.

4) A report (which should include your answer to Question 1 and your test results

with screen shots)