After each loop iteration, u and v only get smaller, and at least one of // them shrinks by at least a factor of two. for { // If both u and v are odd, subtract the smaller from the larger. // If u = v, we need to subtract from v to hit the modified exit condition. if u.IsOdd() == yes && v.IsOdd() == yes { if v.cmpGeq(u) == no { u.sub(v) A.Add(C, &Modulus{nat: m}) B.Add(D, &Modulus{nat: a}) } else { v.sub(u) C.Add(A, &Modulus{nat: m}) D.Add(B, &Modulus{nat: a}) } } // Exactly one of u and v is now...