## Questions

Show that the above algorithm computes the GCD of and .
Assume that and are two machine integers. Let and the number of bits (in binary-expansion) of and 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 .
Adapt the above algorithm for computing GDCs in , that is for univariate polynomials with integer coefficients modulo .

Marc Moreno Maza
2008-03-18