A systolic algorithm for extended GCD computation

96. A. W. Bojanczyk and R. P. Brent, A systolic algorithm for extended GCD computation, Comput. Math. Applic. 14 (1987), 233-238. MR 88m:11110.

Paper: pdf (602K).


For given positive integers a, b the extended GCD problem is to find integers u, v, g such that ua + vb = g, where g is the greatest common divisor of a and b. There are many number-theoretic applications of the extended GCD, for example in error correcting codes and integer factorization. A common case is that g is known to be 1 and we want to compute a multiplicative inverse modulo b, i.e. compute u such that ua = 1 (mod b).

We describe an efficient algorithm which requires O(n2) bit operations (where a and b may be represented in n bits) but is easily pipelined. Thus, using O(n) pipeline stages or O(n) systolic cells, the result can be computed in time O(n). We compare our algorithm with an alternative algorithm proposed by Purdy; ours appears to be superior in both the average case and the worst case. We also give an algorithm for reducing rational numbers to standard form.


An earlier version appeared in Proc. Ninth Australian Computer Science Conference, special issue of Australian Computer Science Communications 8 (1986), 129-137; and as Report CMA-R29-85, CMA, ANU, September 1985, 15pp.

For related work see [77, 79, 82].

Go to next publication

Return to Richard Brent's index page