Unfortunately, except in simple cases, the prime factorization is difficult to compute, and Euclidean algorithm leads to a much easier (and faster) computation. This algorithm consists of replacing of the input by , where is the remainder of the Euclidean division of by , and repeating this operation until getting a zero remainder, that is a pair . This process terminates, because, at each step, the norm of the second Gaussian integer decreases. The resulting is a greatest common divisor, because (at each step) and have the same divisors as and , and thus the same greatest common divisor.