 If one uses the Euclidean algorithm and the elementary algorithms for multiplication and division, the computation of the greatest common divisor of two integers of at most bits is formula_21 This means that the computation of greatest common divisor has, up to a constant factor, the same complexity as the multiplication.However, if a fast multiplication algorithm is used, one may modify the Euclidean algorithm for improving the complexity, but the computation of a greatest common divisor becomes slower than the multiplication.More precisely, if the multiplication of two integers of bits takes a time of , then the fastest known algorithm for greatest common divisor has a complexity formula_22 This implies that the fastest known algorithm has a complexity of formula_23

Previous complexities are valid for the usual models of computation, specifically multitape Turing machines and random-access machines.