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).
Abstract
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.
Comments
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