CSci 4554 Lab 2: Extended Euclidean Algorithm; primality checking

Due Friday, March 10th at 11:59pm (by e-mail)

30 points total

This lab is done in groups of 2.

Task 1: Extended Euclidean Algorithm

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:

  1. Coefficients S and T that solve the equation 1014 * S + 715 * T = 13
  2. Multuiplicative inverse of 25 modulo 1014
  3. Multiplicative inverse of 25 modulo 773

Task 2: primality testing

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.

  1. 202459425811
  2. 583903351639
  3. 188336015890423
  4. 990305520992453
  5. 653219046269215609
  6. 716242718235208469

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.

What to submit (by e-mail to me, CC your partner)

  1. All your program code (well-documented) and instructions for running it.
  2. The answers to the questions, with explanations if needed

CSci 4554 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.