Jebelean-Weber's algorithm without spurious factors
Tudor Jebelean and Ken Weber introduced an algorithm for finding (a, b)-pairs satisfying au + bv = 0 (mod k), with 0 < \a\, \b\ < root k. It is based on Sorenson's "k-ary reduction". This algorithm does not preserve the GCD and its related GCD algorithm has an O(n(2)) time bit complexity in the worst case. We present a modified version which avoids this problem. We show that a slightly modified GCD algorithm has an O(n(2)/ log n) running time in the worst case, where n is the number of bits of the larger input. (c) 2007 Elsevier B.V. All rights reserved.
algorithms integer greatest common divisor (gcd) parallel gcd algorithm extended gcd algorithm analysis of algorithms number theory