Algorithm (3): Modern way to find a multiplicative inverse

Input: Polynomials A ( x ) , P ( x ) .

Output: T ( x ) , the multiplicative inverse of A ( x ) .

1) Set T 0 ( x ) = 0 , T 1 ( x ) = 1 .

2) q ( x ) = P ( x ) d i v A ( x ) , r ( x ) = P ( x ) + q ( x ) A ( x ) .

3) T ( x ) = q ( x ) T 1 ( x ) + T 0 ( x )

4) If r i ( x ) = 1 then return T ( x ) , stop.

5) Else P ( x ) = A ( x ) , A ( x ) = r ( x ) .

T 0 ( x ) = T 1 ( x ) , T 1 ( x ) = T ( x ) .

6) Go to 2