Certification of algorithm 386 [A1]

Subroutine GCDN, Algorithm 386 as described in [1, 2], computes the greatest common divisor, IGCD, of n integers A(1), … , A(n) by using the Euclidean algorithm to compute first gcd(A(1), A(2)), then gcd(gcd(A(1), A(2)), A(3)), etc. It also computes integer multipliers Z(1), … , Z(n) such that IGCD = ∑ni=1 A(i)Z(i).

View this article in the ACM Digital Library.