A generalization of the binary GCD algorithm

Tudor Jebelean

1993 · 59 citations · 9 references

DOIFull text

Open access

Concepts

Abstract

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.

References

9