AbstractWe 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.