2023 1 Using any programming language of your choice implement the Extended Euclidean algorithm Please note that your submission is expected | Assignment Collections

 1) Using any programming language of your choice implement the Extended Euclidean algorithm. 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 two inputs 1) An integer a, which is the modulus 2) A non-negative integer b that is less than a. The program should output three values 1) gcd(a,b) 2) Integer x and 3) Integer y, such that ax + by = gcd(a,b)

Test 1

1) Run your program with a = 1759 b = 550

2) What are your outputs?

3) What is the modular multiplicative inverse of 550 mod 1759?

Test 2

1) Run your program with a = 43 b = 17

2) What are your outputs?

3) What is the modular multiplicative inverse of 17 mod 43? Note that the modular multiplicative inverse has to be non-negative and less than 43.

Test 3

1) Run your program with a = 400 b = 10 2) What are your outputs?

3) What is the modular multiplicative inverse of 10 mod 400? Be mindful of the gcd value to answer this question

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-kickass- readme-7ac01da88ab3 and here

 https://www.youtube.com/watch?v=RZ5vduluea4. 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 https://www.youtube.com/watch?v=vye0kV5gvkA 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 results for Test 1, Test 2 and Test 3 with screen shots)