Write a C++ program following the instructions below. Please follow the order of the tasks given below, and write one function a time, test it, and then move on to the next function. 1. Implement Euclidean Algorithm for calculating greatest common divisor First write and test a function that calculates the greatest common divisor of two nonnegative integers, as follows: / * precondition: a>=b>=0?/ /? postcondition: return d=gcd(a,b)?/ int EuclidAlgGCD (int a, int b ); Then implement the extended Euclidean Algorithm to find not only the greatest common divisor of two integers, but also find the integer coefficients that expresses the gcd in terms of the integers, as illustrated below: /? precondition: a>=b>=0?/ /? postcondition: return d=gcd(a,b),s and t are set so that d=sa+tb?/ int ExtendedEuclidAlgGCD (int a, int b, int \& s, int \& t ); 2. Modular arithmetic Write a function that returns the result of any integer modulo of n (i.e., reduce the integer modulo n ). Note that the C++ operator % can be used, but it returns a negative value, for example, ?1%3 yields -1 , so we need to do something adjustment (recall that ?1mod3=2 because ?1=(?1)×3+2). Therefore, we will use the mod() function from this step to implement the later encode() and decode() functions.
3. Find Relatively Prime Write a function to return a number that is relatively prime with the given number. /* return an integer that is relatively prime with n, and greater than 1 i.e., the god of the returned int and n is 1 Note: Although gcd(n,n?1)=1, we don't want to return n?1 * / int RelativelyPrime (int n ) 4. Find Inverse Then implement the following function, which returns the inverse modulo, and test it. Note that you need to check whether a and n are relative prime before calling this function. Recall that a and n are relatively prime means that gcd(a,n)=1, i.e., their greatest common divisor is 1 . Also recall that the extended Euclidean Algorithm can find the integer s and t for a and n such that as+nt=gcd(a,n), where s is the inverse of a modulo n.
1. Pick two prime numbers p,q, for example, - const int P=23; - const int Q=17; - int PQ=P?Q; 2. Find a e that is relatively prime with (p?1)(q?1) Call RelativelyPrime () 3. Calculate the inverse modulo (p?1)(q?1) of e to be your d Use inverse () 4. Write a function Encode as follows: - // Return M^e mod PQ - int Encode (int M, int e, int PQ ); 5. Write a function Decode as follows: - //Return C?d mod PQ - int Decode (int C, int d, int PQ ); 6. Verify that RSA algorithm works, i.e., - int M; - / * M is an integer that is smaller than PQ?/ - cout << "Enter an integer that is smaller than" <<PQ; - cin<<M; - C= Encode (M,e,PQ); - M1= Decode (C,d,PQ); - assert (M==M1); //Note: include assert.h header file to use this //macro/function.
1. Due to the c++ compiler issue, c++ might cannot handle the operation of raising an integer to a large power. Here is an instance of p and q that can work: p=3,q=7?pq=21,(p?1)(q?1)=12, pick e=5, then d=5(5?5mod12=1, so 5 is the inverse of 5mod12 ) 2. If we want to randomly generate two initial prime numbers, then we need a function to test primality. Use the definition of prime number to guide your implementation of the following function. For any positive integers n,r, s, if n=rs, then r<=sqrt(n) or s<=sqrt(n) / return true if n is prime return false if n is not prime Precondition: n>1 bool IsPrime (int n )