A generalization of the binary GCD algorithm
Tudor Jebelean · 1993
A generalization of the binary algorithm for operation at 'word level" by using a new concept of 'modular conjugates" computes the GCD of multiprecision integers two times faster than Lehmer-Euclid method.Most importantly, however, the new algorithm is suitable for systolic parallelization, in 'least-significant digits jirst" pipelined manner and for aggregation with other systolic algorithms for the arithmetic of multiprecision rational numbers.