## 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(*n*^{2}) 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