First of all we find the 2-adic values (say *m* and *n*) of *a* and
*b* and also replace *a* and *b* by *a*/2^{m} and *b*/2^{n} respectively.
As we saw above this can be done in time that is linear in the size of
*a* and *b*. Let *k* denote the minimum of *m* and *n*. We now begin
the iterative step.

For this iteration *a* and *b* will always be odd. First we compute
*c* - ^{ . }*M*^{p} = *a* - *b* (where is the ``borrow''). If = 1,
then we replace *c* by its bitwise negation
(*c*) and then add 1
(this replaces *c* by *M*^{p} - *c*; the sign of *c* is then
(- 1)^{}).
If *c* is zero then the GCD is
2^{k . }*a*. Otherwise, we calculate
the 2-adic value *l* of *c* and replace *c* by *c*/2^{l} so that *c* is
odd once more. Since *l* is usually a smaller than log(*M*) this
step is linear in the size of *c*. Now if = 1 then we replace
*b* by *c* and if = 0 then we replace *a* by *c* and iterate.
(Thus we replace *a* if it is larger and *b* if it is larger).

Note that this involves no divisions at all. Thus it can be very fast
in principle. Each iteration reduces the size of the largest of *a*
and *b* by at least one bit. Thus there are at most as many steps as
log_{2}(*a*). Moreover, if *a* = 2^{N} - 1 and *b* = 1, then we can see that
the process takes exactly *N* steps. Thus, quite often an initial
division is performed in order to ensure that *a* and *b* have roughly
the same size (this condition reduces the number of iterations for all
GCD algorithms).