We investigate a variant of the so-called "binary" algorithm for finding the GCD (greatest common divisor) of two numbers which requires no comparisons. We show that when implemented with carry-save hardware, it can be used to find the modulo B inverse of an n-bit binary integer in a time proportional to n, using only registers of length proportional to n.
Such a hardware implementation of this algorithm set up for finding inverses with respect to a 336 bit modulus B would have applications in the currently expanding field of secure data transmission and storage.
In such an implementation, multiplication in linear time-both modulo B and ordinary-would come along as a by-product because multiplication can be achieved by a sequence of nine inversions, some additions and negations. THE ALGORITHM Carry-save addition was known to van Neumann, and has been implemented on several machines-for example the ILLIAC III (we refer the reader to Kai Hwang's invaluable book [2]. In modern parlance it could be called a "parallel" method for addition, since all of the digits can be processed simultaneously. If two numbers A and B in binary two's complement representation are added to a third such number C, the result can be written as U + V, where V may be viewed as the sequence of carries, and this may be accomplished entirely by local operations in one cycle. (This works because 1 + 1 + 1 = 3 has only two digits in its binary representation.) Thus carry ripple is totally eliminated. If we wish to add together two numbers in carry-save form-say A + B and C + D-then we first add C to A + B obtaining U + V and then add D to U + V obtaining Y + Z. Trouble comes if we ever wish to leave carry-save form, since we must then do a true sum of A and B to convert A + B to the usual binary form, and carries will usually occur. Another difficulty is that it is time-consuming to compare two numbers A + B and C + D in carry-save form, since we may have A > C and yet B <D. It is even difficult to test whether for example A + B is equal to C + D. However it is very easy to test whether a number A + B is even and to divide by two if it is, and the negation -(At B) can also be found quickly. (This is necessary because A and B separately are in two's complement form.)
Euclid's algorithm is the most well known method for finding the GCD of two integers, just as Euclid's extended algorithm is the usual method for finding the coefficients R and S such that RA-SB equals the GCD of A and B. Indeed, so strong is the association between the name Euclid and GCD's that it is a real effort to think of the problem and the algorithm as separate. Euclid's algorithm is ruled out of this discussion because of the divisions and comparisons it requires.
A binary method for calculating the greatest common divisor of two integers A and B, as well as the coefficients R and S such that RA-SB is the GCD has been discussed in Knuth's second volume, with some useful additional comments in the new edition [l]. We are concerned here with a variant that Knuth does not analyze, although we were apparently not the first to think of it.
Suppose we wish to compute the GCD of two numbers A and B. Having removed all powers of two shared by A and B, we may assume that the GCD of A and B is odd. We then obtain A' and B' from A and B as follows: We put the vector (A', B') equal to
(1) (A/2, B) if A is even.
(2) (A, B/2) if B is even.
(3) ((A t B)/2, (A -B)/2) if A and B are both odd (the only remaining possibility).