CISC2100: Discrete Structur LAB Class 3

Feel free to write the program in any language of your perference. The hint below is given in C++ syntax.

1. Practice modular arithmetic

First write a function that returns the result of any integer modulo of n (i.e., reduce the integer modulo n). Please note that the C++ operator % can be used, but it returns a negative value, e.g., -1 % 3 yields -1, but we -1 mod 3 = 2 as -1= (-1)*3+2.

/* n is greater than 1
   a can be negative
   return a mod n (as defined in class) 
    a mod n = r if and only if a = nk+r, 0 =< r > d 
*/
int mod (int a, int n); 

Then, write and test three functions to perform modular addition, subtraction, multiplication.

/* modular n addition
 The parameter n > 1 
 return (a+b) mod n
 Note that the return value needs to be between 0 and n-1 
*/ 
int add (int a, int b, int n); 

2. Write and test Euclidean Algorithm

Write and test a function that calculates the greatest common divisor of two integers (you can assume that they are both non-negative), and also find out the integer coefficients (as discussed in class), that expresses the gcd in terms of the two integers.

/* precondition: a >=b>=0 */
int gcd (int a, int b, int & s, int &t)
{
   assert (a<=0 && b<=0 && a<=b);

   if (b==0){
	s = 1; 
	t = 0;
	return a; //a = a*1+b*t;
   }
   else {
	int s1,t1;
        int q = a/b;
        int r = a%b;
        int d = gcd (b, r, s1, t1);
	s = t1; 
	t = s1-q*t1;
	assert (d==(a*s+b*t)); //EZ: Please add #include <assert.h>
	return d;
   }
   
}

Please submit a hardcopy of your proof that the above function works, i.e., for any integer a,b such that a >=b>=0, gcd (a,b,s,t) returns d, the greatest common divisor of a,b, and sets s, t such that as+bt=d, using the template provided in class.

3. Write a function that returns the inverse modulo

Write a function with the following functionality, and test it. Note that you need to check whether a and n are relative prime before calling this funciton.

Hint: Please refer to Corollary 8.4.7 (it's discussed in class) on page 489 for how..

/* n>1, a is nonnegative */ 
/* a and n are relative prime to each other */
/* return s such that a*s mod n is 1 */
int inverse (int a, int n);

4. Write a function to calculate modular exponents

In RSA encoding and decoding algorithm, we need to calculate modular exponents (with a large exponent).

Basic requirement: you can use a loop to raise a for m times, making sure that you reduce the result modulo n in each step. Extra credits:: use two exponent rules to speed up this calcuation (read textbook 484-485 for details), i.e., with less multiplication operations. Hint: You can use the logic studied in decimal to binary conversion.

/* return a^m mod n 
   where n > 1 
  Two exponent rules are used to cut down the number of multiplication operations:  
   a^(2k)=(a^k)^2
   a^(k+j)=a^k * a^j 
*/ 
int exp (int a, int m, int n)

5. Verify Fermat's Little Theorem

Write a function to verify for this theorem, you want to use the functions that you have written so far in implementing this.

/* If p is any prime number and a is any integer such that p does not divide a,then a^{p−1} ≡1(modp). */
//return true if a^{p-1}=1 mod p 
bool FermatTesting (int p, int a) 

Note that for any interger p, if p does not divide a, and the above testing return false, then p is not a prime number.

On the other hand, for any interger p, if p does not divide a, and the above testing return true, we cannot conclude that p is a prime number. So the above function can be used to rule out a given integer from being a prime.

6. Find Relative Prime

Write a function to return a number that is relative prime with the given number.

/* return a integer that is relative prime with n, and greater than 1 
  i.e., the gcd of the returned int and n is 1 
*/
int RelativePrime (int n) 

1. Pick two prime numbers p,q (you can try small primes first), e.g.,

   const int P=23;
   const int Q=17;
   int PQ=P*Q;
   

2. Find a d that is relatively prime with (p-1)(q-1) (call the RelativePrime() function).
3. Calculate the inverse modulo (p-1)(q-1) of d to be your e, use the inverse function.
4. Write a function Encode as follows:

   int Encode (int M, int d, int PQ); 
   

5. Write a function Decode as follows:

   int Decode (int C, int e, int PQ); 
   

6. Verify that RSA algorithm works, i.e.,

   int M;
   
   /* M is an integer that is smaller than PQ */
   cout <<"Enter a integet that is smaller than "<< PQ;
   cin <<M;
   
   C=Encode (M, d, PQ);
   M1=Decode (C, e, PQ);
   assert (M==M1);
   

You can submit the project using mail command:

mail -s "cs2100: lab3" xzhang@fordham.edu < rsa.cpp