Questions

$(1)$

Show that the above algorithm ${\gcd}(a,b)$ computes the GCD of $a$ and $b$ .

$(2)$

Assume that $a$ and $b$ are two machine integers. Let $n_a$ and $n_b$ the number of bits (in binary-expansion) of $a$ and $b$ respectively. Give an upper bound for the number of machine word operations (comparison of two machine integers, subtraction, shift, accessing a bit of a machine integer) needed for computing ${\gcd}(a,b)$ .

$(3)$

Adapt the above algorithm for computing GDCs in ${\mbox{${\mathbb{Z}}$}}/2{\mbox{${\mathbb{Z}}$}}[x]$ , that is for univariate polynomials with integer coefficients modulo $2$ .