1. Problem Description The greatest common divisor gcd (a, b) between two positive integers a and...

Transcribed Image Text:

1. Problem Description The greatest common divisor gcd (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. GCD is a very powerful tool in modern cryptography, and when the target integers to be calculated are small (less than 108), GCD can be calculated in a few seconds with a naïve 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 naïve 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, you will need to calculate the GCD of two big integers efficiently. 2. Input Format One line containing two integers, a and b, where 0 < a, b < 10256 3. Output Format An integer representing gcd (a, b) with a single end-of-line (endl). 4. Sample Input/Output Sample Input 1 20230925 52903202 Sample Output 1 11 Sample Input 2 111111222222333333444444555555 666666777777888888999999 Sample Output 2 333333 1. Your program must be written in C/C++ language and can be compiled Linux platform. on the To deal with the big integers, we need a "data structure", such as an integer array in C to represent larger values. For instance, you can use an integer array where each element represents one (decimal) digit, like representing 202309 by the following code snippet. vector<int> digits = {9, 0, 3, 2, 0, 2); It is not required to use the representation above, though. You can use any representation that facilitates your implementation. Algorithm: 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 1 ans ans x 2, n + n/2,m+m/2 else if n is even then In n+ n/2 else if m is even then m+m/2 end if n > m then swap(n, m) m← (m-n) end return n x ans 1. Problem Description The greatest common divisor gcd (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. GCD is a very powerful tool in modern cryptography, and when the target integers to be calculated are small (less than 108), GCD can be calculated in a few seconds with a naïve 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 naïve 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, you will need to calculate the GCD of two big integers efficiently. 2. Input Format One line containing two integers, a and b, where 0 < a, b < 10256 3. Output Format An integer representing gcd (a, b) with a single end-of-line (endl). 4. Sample Input/Output Sample Input 1 20230925 52903202 Sample Output 1 11 Sample Input 2 111111222222333333444444555555 666666777777888888999999 Sample Output 2 333333 1. Your program must be written in C/C++ language and can be compiled Linux platform. on the To deal with the big integers, we need a "data structure", such as an integer array in C to represent larger values. For instance, you can use an integer array where each element represents one (decimal) digit, like representing 202309 by the following code snippet. vector<int> digits = {9, 0, 3, 2, 0, 2); It is not required to use the representation above, though. You can use any representation that facilitates your implementation. Algorithm: 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 1 ans ans x 2, n + n/2,m+m/2 else if n is even then In n+ n/2 else if m is even then m+m/2 end if n > m then swap(n, m) m← (m-n) end return n x ans

Answer rating: 100% (QA)

For calculating the greatest common divisor GCD of two large integers efficiently in C on a Linux sy... View the full answer