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$ .

Marc Moreno Maza
2008-03-18