Algorithm (1): Euclidean algorithm [3]

Input: Polynomials $A\left(x\right),P\left(x\right)$ .

Output: $\gcd \left(A\left(x\right),P\left(x\right)\right)$ .

1) While $A\left(x\right)\ne 0$ do

a) $r\left(x\right)=P\left(x\right)\mathrm{mod}A\left(x\right)$ , $P\left(x\right)=A\left(x\right)$ , $A\left(x\right)=r\left(x\right)$ .

2) Return $P\left(x\right)$ .