Instructor: Jeremy Johnson

Due Wed. Feb. 2 in class

MDEXP computes the integer power of an element in Z_m using a fast algorithm whose computing time is dominated by log(m). MDINV computes the inverse, assuming it exists, of an element in Z_m. The inverse of a in Z_m exists if and only if gcd(a,m) = 1. MDINV uses the half-extended Euclidean algorithm. Recall that if gcd(a,m) = 1, then there exists integers x and y such that a*x + m*y = 1, which implies that a*x is equivalent to 1 modulo m, hence x is the inverse of a in Z_m. The half-extended Euclidean algorithm computes x, but not y, using the same process as the extended Euclidean algorithm. For this application, we do not need y, hence there is not point in computing it.

An alternative approach to computing modular inverses relies on Fermat's theorem. This theorem states that a^{p-1} is equivalent to 1 modulo p, for all a not a multiple of p, when p is a prime number. This theorem implies that a * a^{p-2} is equal to 1 in Z_p, hence a^{-1} is equal to a^{p-2}. Thus the inverse of a in Z_p can be computed by raising a to the (p-2)-nd power in Z_p. This can be computed efficiently using MDEXP or a similar algorithm.

In this assignment you will compare the efficiency of these two approaches to computing modular inverses.

- The SACLIB function MDEXP computes powers in Z_m, where m is a BETA-digit. This is performed using an iterative version of the binary powering algorithm discussed in class. The computing time is dominated by L(m). First examine the code for MDEXP and then prove that MDEXP(m,a,n) correctly computes a^n in Z_m.
- Write a C function with the same specifications as MDINV with the further requirement that m is a prime number. Your function should compute the inverse of an element in Z_m using Fermat's theorem and a fast algorithm for computing powers such as that used by MDEXP (you may call this function directly or you may inline the code in MDEXP). Verify that your function is correct by comparing its output to the output of the SACLIB function MDINV.
- Write a function to time and compare the SACLIB function MDINV and the function you wrote in the previous exercise. You should time each program with the same inputs. Furthermore, you should generate a k-bit prime number, p, for k = 10,...,28, and then time the computation of a^{-1} in Z_p using both algorithms. You can generate a k-bit prime number by starting with 2^{k-1} and looking at successive odd numbers until you detect a prime. You can use the SACLIB function IFACT to determine if a number is prime or not. IFACT returns a list containing the prime factors of a number. You can call this function and then use the function LENGTH to see if there is more than one factor. After generating p, you can use MDRAND to generate a random element of Z_p to use as input to MDINV.