Worst-case analysis of Weber's GCD algorithm
Recently, Ken Weber introduced an algorithm for finding the (a, b)-pairs satisfying au + by equivalent to 0 (mod k), with 0 < \a\, \b\ < root k where (u, k) and (u, k) are coprime. It is based on Sorenson's and Jebelean's "k-ary reduction" algorithms. We provide a formula for N(k), the maximal number of iterations in the loop of Weber's GCD algorithm. (C) 1999 Elsevier Science B.V. All rights reserved.
integer greatest common divisor (gcd) complexity analysis number theory