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

*
*

2008-03-18