Problem 1 - Greatest Common Divisor of Big Integers (Program- ming) Problem Description The greatest common divisor god(a,b) between two positive integers a and b is defined as the largest positive integer that divides both a and b without a remainder. Mathematically speaking, for any positive integers a and b, ged(a,b) satisfies the following properties: a = 0 mod ged(a,b) b = 0 mod god(a,b) Vk e N and k > gcd(a,b), (a # 0 mod k) or (6 0 mod k) GCD is a very powerful tool in modern cryptography, and when the target integers to be calculated are small (less than 10%), GCD can be calculated in a few seconds with a nave method. However, the numbers in modern cryptography requires at least 512 digits to prevent attackers from using a brute-force method to derive the secret key. This required number is too large for the nave methods to calculate GCD in a reasonable time and the numbers exceeds the limit of even long long in the C language. In this problem, we will guide you to calculate the GCD of two big integers efficiently. Implementation First, to deal with the big integers, we need a "data structure", such as an integer array in C to represent larger values. We will call it BigInt. For instance, you can use an integer array where each element represents one (decimal) digit, like representing 17202 by the following code snippet. int digits [10] ={2,0,2,7,1}; It is not required to use the representation above, though. You can use any representation that facilitates your implementation of the following algorithm. It is an opportunity to think about how well-designed data structures" can lead to "efficient algorithms." Next, please implement the following algorithm, called Binary Algorithm, using the C language. Then you will miraculously get the correct GCD. Note that you need to implement four components: a comparator between two BigInts, subtraction between two BigInts, division by 2 for one BigInt, and multiplication by 2k for one BigInt with some k. It is strongly recommended to implement the four components as separate functions, and test their correctness separately, before combining them with the Binary Algorithm. Algorithm 1: Binary Algorithm for Greatest Common Divisor Input: Two positive integers a and b. Output: A positive integer ans representing greatest common divisor of a and b. nmin(a,b), m = max(a,b), ans + 1 while n +0 and m 0 do if n is even and m is even then ans ans x 2, n = n/2, mm/2 else if n is even then In+ n/2 else if m is even then | mm/2 end if n >m then swap(n,m) m ( mn) end return n x ans Problem 1 - Greatest Common Divisor of Big Integers (Program- ming) Problem Description The greatest common divisor god(a,b) between two positive integers a and b is defined as the largest positive integer that divides both a and b without a remainder. Mathematically speaking, for any positive integers a and b, ged(a,b) satisfies the following properties: a = 0 mod ged(a,b) b = 0 mod god(a,b) Vk e N and k > gcd(a,b), (a # 0 mod k) or (6 0 mod k) GCD is a very powerful tool in modern cryptography, and when the target integers to be calculated are small (less than 10%), GCD can be calculated in a few seconds with a nave method. However, the numbers in modern cryptography requires at least 512 digits to prevent attackers from using a brute-force method to derive the secret key. This required number is too large for the nave methods to calculate GCD in a reasonable time and the numbers exceeds the limit of even long long in the C language. In this problem, we will guide you to calculate the GCD of two big integers efficiently. Implementation First, to deal with the big integers, we need a "data structure", such as an integer array in C to represent larger values. We will call it BigInt. For instance, you can use an integer array where each element represents one (decimal) digit, like representing 17202 by the following code snippet. int digits [10] ={2,0,2,7,1}; It is not required to use the representation above, though. You can use any representation that facilitates your implementation of the following algorithm. It is an opportunity to think about how well-designed data structures" can lead to "efficient algorithms." Next, please implement the following algorithm, called Binary Algorithm, using the C language. Then you will miraculously get the correct GCD. Note that you need to implement four components: a comparator between two BigInts, subtraction between two BigInts, division by 2 for one BigInt, and multiplication by 2k for one BigInt with some k. It is strongly recommended to implement the four components as separate functions, and test their correctness separately, before combining them with the Binary Algorithm. Algorithm 1: Binary Algorithm for Greatest Common Divisor Input: Two positive integers a and b. Output: A positive integer ans representing greatest common divisor of a and b. nmin(a,b), m = max(a,b), ans + 1 while n +0 and m 0 do if n is even and m is even then ans ans x 2, n = n/2, mm/2 else if n is even then In+ n/2 else if m is even then | mm/2 end if n >m then swap(n,m) m ( mn) end return n x ans