Assignment 4

CS 680-503 Computer Algebra I
Instructor: Jeremy Johnson 
Due Wed. Feb. 2 in class

  In this assignment you will need to write a C program that calls and times SACLIB algorithms. See the previous lecture notes for an example and some introductory information.

Overview

SACLIB provides a variety of routines for performing computation in Z_m, the ring of integers modulo m. The elements of Z_m are represented by the integers {0,...,m-1}. These routines are divided into two classes: algorithms where m is a BETA-digit (a number less than BETA = 2^29, i.e. a number with a single digit in base BETA number system) and algorithms where m is an arbitrary positive integers. Functions whose inputs are in Z_m, where m is a BETA-digit have names beginning with the letters MD (modular digit) and functions where m is an arbitrary integer have names begining with the letters MI (modular integer). This distinction is made for efficiency purposes. Let Z_m denote the integers mod m. In this assignment you will investigate the functions MDEXP and MDINV (use the command sman to see the specifications and source code for these functions).

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.

Problems to Hand in

  1. 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.
  2. 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.
  3. 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.