This lab is done in groups of 2.
You goal is to implement and test the
Extended Euclidean algorithm (also given in the textbook). It must be implemented as a function
(or a method) that takes r0, r1 as parameters. You also need to write an interactive
program that reads two numbers from the user and passes them to your function.
You may use any programming language, as long as it runs in the CSci labs and you
provide clear instructions for how to run it and how to pass data to it.
Test your program to compute the following:
Write a program that reads in an integer number and checks if it is prime.
Try to make it reasonably efficient, but don't use any sophisticated primality
testing methods (such as probabilistic testing).
Your integers should be stored as BigInteger or equivalent, so that they can be
arbitrarily large.
As in Task 1, allow entering input on the command line.
Can you determine if the following numbers are prime? Please submt your result.
If the number isn't prime, please specify its divisors. If your program times out, indicate how long it was running.
If the length of number you are checking is increased by one decimal digit, approximately by how much does the worst case of your algorithm change? Please explain your answer clearly.