GCD binary representation time complexity

Question

1.  Consider the following algorithm for deciding GCD:

“On input :

1. If z doesn’t divide x or y, reject.               O(n)

2. For i from z + 1 to min(x,y) do:                  O(2^n)

    2.1. If i divides both x and y, reject.         O(n)

3. Accept.”                                           O(1)

Analyze the algorithm’s time complexity (in big-O notation).

n is the length of the max(x,y) So I was given an algorithm, the time complexity to the right is My addition and not part of this question. I want to make sure this is correct. I was thinking diving binary numbers is O(n) using long devision and step 2 just adds 0 or 1 to each previous number thus making the time exponential. Am I right ? Also, is there an algorithm that solves this in polynomial time ? Thanks

Answer 1

Assuming x <= y and no particularly clever division, it's O (x log x log x), if you don't divide y by I if x is already not divisible by I.

If z divides x and y then you just need to check if gcd (x/z, y/z) = 1. And only test 2 <= I <= sqrt (x) and x itself.