1. Problem Description The greatest common divisor gcd (a, b) between two positive integers a and...
Fantastic news! We've Found the answer you've been seeking!
Question:
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
Expert Answer:
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
Related Book For
Java How To Program Late Objects Version
ISBN: 9780136123712
8th Edition
Authors: Paul Deitel, Deitel & Associates
Posted Date:
Students also viewed these programming questions
-
Thandiworks as a portfolio manager at VBS bank, which is a registered financial services provider. Over the weekend, she attended a friend'sbraaiparty.Nandi, a friend of hers, mentioned that she was...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Consider the Cobb-Douglas production function f(x, y) = 300x0.85, 0.15 When x = 4000 and y = 800, find the following. (Round your answers to two decimal places.) (a) the marginal productivity of...
-
Liberty Ventures Inc. reported a $320,000 profit in 2020 and declared preferred dividends of $20,000. The following changes in common shares outstanding occurred during the year: Jan 1 100,000 common...
-
Selected ratios for two retailers follow, along with the industry averages: Instructions (a) Compare the profitability of Bargain Hunters with that of Discount Paradise, and with the industry...
-
Q Restaurant Group Holdings, LLC, owns and operates Q-BBQ restaurants. Michael Lapidus managed the restaurants and conducted the day-to-day operations. This included bargaining with the restaurants...
-
A sample of 32 students took a class designed to improve their SAT math scores. Following are their scores before and after the class. Can you conclude that the mean increase in score is less than 15...
-
After the presentation of your report on the examination of the financial statements to the board of directors of Piper Publishing Company, one of the new directors expresses surprise that the income...
-
"Advertising reflects the mores of society, but it does not influence them." --David Ogilvy Ogilvy argues that advertising does not influence a society's accepted customs and attitudes, it merely...
-
Aggie Oil Corporation, a new successful efforts company, incurred the following costs and made the other transactions shown below for the years 2018 and 2019. 2018 a. Paid $225,000 for G&G costs...
-
Problem 4. Let Utt = 94xx u(0,x) = 0 ut(0, x) = f(x), where f(x)=1 for 0 < x < 1 and 0 otherwise. Find the function u(2,x).
-
Pearl Products Limited of Shenzhen, China, manufactures and distributes toys throughout South East Asia. Three cubic centimeters ( cc ) of solvent H 3 0 0 are required to manufacture each unit of...
-
First, write the value(s) that make the denominator(s) zero. Then solve the equation. 18 15 +3=x-1
-
ABC Companys budgeted sales for June, July, and August are 1 4 , 6 0 0 , 1 8 , 6 0 0 , and 1 6 , 6 0 0 units respectively. The selling price for each unit is $ 1 2 . Based on past experience, ABC...
-
Consider this formula. z = y |* If z = 4.0 and y = 8.8, what is the value of x? Express your answer to the tenths place (i.e., one digit after the decimal point).
-
Solve 35 9 11. Round to the nearest thousandth as needed.
-
Given: In this question, the given values are, A 3q, 208V, f = 60Hzinduction motor runs at N = 1746 rpm when it delivers rated output power. To find the value of the stator rotating field.
-
Ann hires a nanny to watch her two children while she works at a local hospital. She pays the 19 year-old nanny $125 per week for 48 weeks during the current year. a. What is the employers portion of...
-
The recursive Towers of Hanoi. Write a animated solution to the Towers of Hanoi that shows the disks moving between pegs. Allow the user to enter the number of disks.
-
Heres a peek ahead. In this chapter, you learned about integers and the type int. Java can also represent floating-point numbers that contain decimal points, such as 3.14159. Write an application...
-
Many programs written with inheritance could be written with composition instead, and vice versa. Rewrite class BasePlus-CommissionEmployee (Fig. 9.11) of the...
-
Derive the equation of motion and natural frequency for mass \(m\) shown in Figure 2.57. Assume the pulleys are massless, the cable is inextensible, and let the spring constant be \(k\). eeeee k...
-
Derive the equation of motion and natural frequency for mass \(m\) shown in Figure 2.58. Assume the pulleys are massless, and let the spring constants be \(k_{1}\) and \(k_{2}\). Let \(x_{1}\) and...
-
Show that the period of free vibration of a load weighing \(W\) suspended from two parallel springs, as shown in Figure 2.59, is given by \(T\), \[ T=2 \pi \sqrt{\frac{W}{g\left(k_{1}+k_{2} ight)}}...
Study smarter with the SolutionInn App