Write a C++ program following the instructions below. Please follow the order of the tasks given...

   

Transcribed Image Text:

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 non- negative 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-1 mod 3 = 2 because -1= (-1)×3+2). Therefore, we will use the mod() function from this step to implement the later encode() and decode() functions. /* precondition: n is greater than 1, a can be negative postcondition: return a mod n (as defined in class) a mod n =r if and only if a = nk+r, 0 =<r <n (note that r needs to be non-negative). int mod (int a, int n); 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 gcd 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. /* n>1, a is nonnegative */ /* a< n */ /* 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). ( int s, t; int d ExtednedEuclidAlgGCD (n, a, s, t); if (d==1) ( } else ( } return (mod (t, n)); //t might be negative, use mod() to reduce to // an integer between 0 and n-1. cout <<"a and n are not relatively prime!\n"; 5. Practice with RSA algorithm 1. Pick two prime numbers p, q, for example, ● 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 foll ● ● const int P-23; const int Q=17; int PQ-P*Q; 5. Write a function Decode as follows: //Return C^d mod PQ ● int Decode (int C, int d, int PQ); ● // Return M^e mod PQ int Encode (int M, 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 an integer that is smaller than" << PQ; cin <<M; C=1 code (M, e, PQ); M1-Decode (C, d, PQ) ; assert (M=-M1); //Note: include assert.h header file to use this //macro/function. NOTE: 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*5 mod 12 = 1, so 5 is the inverse of 5 mod 12) 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) 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 non- negative 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-1 mod 3 = 2 because -1= (-1)×3+2). Therefore, we will use the mod() function from this step to implement the later encode() and decode() functions. /* precondition: n is greater than 1, a can be negative postcondition: return a mod n (as defined in class) a mod n =r if and only if a = nk+r, 0 =<r <n (note that r needs to be non-negative). int mod (int a, int n); 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 gcd 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. /* n>1, a is nonnegative */ /* a< n */ /* 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). ( int s, t; int d ExtednedEuclidAlgGCD (n, a, s, t); if (d==1) ( } else ( } return (mod (t, n)); //t might be negative, use mod() to reduce to // an integer between 0 and n-1. cout <<"a and n are not relatively prime!\n"; 5. Practice with RSA algorithm 1. Pick two prime numbers p, q, for example, ● 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 foll ● ● const int P-23; const int Q=17; int PQ-P*Q; 5. Write a function Decode as follows: //Return C^d mod PQ ● int Decode (int C, int d, int PQ); ● // Return M^e mod PQ int Encode (int M, 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 an integer that is smaller than" << PQ; cin <<M; C=1 code (M, e, PQ); M1-Decode (C, d, PQ) ; assert (M=-M1); //Note: include assert.h header file to use this //macro/function. NOTE: 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*5 mod 12 = 1, so 5 is the inverse of 5 mod 12) 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)

Answer rating: 100% (QA)

1 Euclidean Algorithm for GCD include int EuclidAlgGCDint a int b while b 0 int temp b b a b a temp ... View the full answer