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