GCD Algorithm

In the name "greatest common divisor", the adjective "greatest" may be replaced by ”highest”, and the word" divisor" may be replaced by" factor", so that other names include greatest common factor (gcf), etc. This impression can be extended to polynomials (see polynomial greatest common divisor) and other commutative rings. Greatest common divisors can in principle be computed by determining the prime factorizations of the two numbers and comparing factors

GCD source code, pseudocode and analysis

The computation of the greatest common divisors belongs thus to the class of problems solvable in quasilinear time. A fortiori, the corresponding decision problem belongs to the class P of problems solvable in polynomial time. The GCD problem is not known to be in NC, and so there is no known way to parallelize it efficiently; nor is it known to be P-complete, which would imply that it is unlikely to be possible to efficiently parallelize GCD computation