Algorithm (2): Extended Euclidean algorithm [3]

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

Output: The multiplicative inverse of $A\left(x\right)$ .

1)Set $y_2\left(x\right)=0$ , $y_1\left(x\right)=1$ .

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

a) $q\left(x\right)=P\left(x\right)divA\left(x\right)$ , $r\left(x\right)=P\left(x\right)+q\left(x\right)A\left(x\right)$ .

b) $y\left(x\right)=y_2\left(x\right)+y_1\left(x\right)q\left(x\right)$

c) $y_2\left(x\right)=y_1\left(x\right)$ , $y_1\left(x\right)=y\left(x\right)$ .

d) $P\left(x\right)=A\left(x\right)$ , $A\left(x\right)=r\left(x\right)$ .

3) Return $y_1\left(x\right)$ .