Editing Extended Euclidean algorithm (section)

=== Simple algebraic field extensions ===

The extended Euclidean algorithm is also the main tool for computing [[multiplicative inverse]]s in [[simple extension|simple algebraic field extensions]]. An important case, widely used in [[cryptography]] and [[coding theory]], is that of [[finite field]]s of non-prime order. In fact, if {{math|''p''}} is a prime number, and {{math|1=''q'' = ''p''<sup>''d''</sup>}}, the field of order {{math|''q''}} is a simple algebraic extension of the [[prime field]] of {{math|''p''}} elements, generated by a root of an [[irreducible polynomial]] of degree {{math|''d''}}.

A simple algebraic extension {{math|''L''}} of a field {{math|''K''}}, generated by the root of an irreducible polynomial {{math|''p''}} of degree {{math|''d''}} may be identified to the [[quotient ring]] <math>K[X]/\langle p\rangle,</math>, and its elements are in [[bijective|bijective correspondence]] with the polynomials of degree less than {{math|''d''}}. The addition in {{math|''L''}} is the addition of polynomials. The multiplication in {{math|''L''}} is the remainder of the [[Euclidean division of polynomials|Euclidean division]] by {{math|''p''}} of the product of polynomials. Thus, to complete the arithmetic in {{math|''L''}}, it remains only to define how to compute multiplicative inverses. This is done by the extended Euclidean algorithm.

The algorithm is very similar to that provided above for computing the modular multiplicative inverse. There are two main differences: firstly the last but one line is not needed, because the Bézout coefficient that is provided always has a degree less than {{math|''d''}}. Secondly, the greatest common divisor which is provided, when the input polynomials are coprime, may be any non zero elements of {{math|''K''}}; this Bézout coefficient (a polynomial generally of positive degree) has thus to be multiplied by the inverse of this element of {{math|''K''}}. In the pseudocode which follows, {{math|''p''}} is a polynomial of degree greater than one, and {{math|''a''}} is a polynomial. 

 '''function''' inverse(a, p)
     t := 0;     newt := 1
     r := p;     newr := a
 
     '''while''' newr ≠ 0 '''do'''
         quotient := r '''div''' newr
         (r, newr) := (newr, r − quotient × newr)
         (t, newt) := (newt, t − quotient × newt)
 
     '''if''' degree(r) > 0 '''then''' 
         '''return''' "Either p is not irreducible or a is a multiple of p"
 
     '''return''' (1/r) × t

====Example====

For example, if the polynomial used to define the finite field GF(2<sup>8</sup>) is {{math|1=''p'' = ''x''<sup>8</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x'' + 1}}, and {{math|1=''a'' = ''x''<sup>6</sup> + ''x''<sup>4</sup> + ''x'' + 1}} is the element whose inverse is desired, then performing the algorithm results in the computation described in the following table. Let us recall that in fields of order 2<sup>''n''</sup>, one has &minus;''z'' = ''z'' and ''z'' + ''z'' = 0 for every element ''z'' in the field). Since 1 is the only nonzero element of GF(2), the adjustment in the last line of the pseudocode is not needed.
{| class="wikitable"
|-
! step
! quotient 
! r, newr
! s, news
! t, newt
|-
!
|  
| {{math|1=''p'' = ''x''<sup>8</sup> + ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x'' + 1 }}
|1
|  0
|-
!
|  
| {{math|1=''a'' = ''x''<sup>6</sup> + ''x''<sup>4</sup> + ''x'' + 1}}
|0
|  1
|-
! 1
| {{math|1=''x''<sup>2</sup> + 1}}
| {{math|1=''x''<sup>2</sup> = ''p'' &minus; ''a'' (''x''<sup>2</sup> + 1)}}
|1
| {{math|1=''x''<sup>2</sup> + 1 = 0 &minus; 1 &middot; (''x''<sup>2</sup> + 1)}}
|-
! 2
| {{math|1=''x''<sup>4</sup> + ''x''<sup>2</sup>}}
| {{math|1=''x'' + 1 = ''a'' &minus; ''x''<sup>2</sup> (''x''<sup>4</sup> + ''x''<sup>2</sup>)}}
| {{math|1=''x''<sup>4</sup>+''x''<sup>2</sup> = 0 &minus; 1(''x''<sup>4</sup>+''x''<sup>2</sup>)}}
| {{math|1=''x''<sup>6</sup>  + ''x''<sup>2</sup> + 1 = 1 &minus; (''x''<sup>4</sup> + ''x''<sup>2</sup>) (''x''<sup>2</sup> + 1)}}
|-
! 3
| {{math|1=''x'' + 1}}
| {{math|1= 1 = ''x''<sup>2</sup> &minus; (''x'' + 1) (''x'' + 1)}}
| {{math|1=''x''<sup>5</sup>+''x''<sup>4</sup>+''x''<sup>3</sup>+''x''<sup>2</sup>+1 = 1 &minus; (''x'' +1)(''x''<sup>4</sup> + ''x''<sup>2</sup>)}}
| {{math|1=''x''<sup>7</sup> + ''x''<sup>6</sup> + ''x''<sup>3</sup> +  ''x'' = (''x''<sup>2</sup> + 1) &minus; (''x'' + 1) (''x''<sup>6</sup>  + ''x''<sup>2</sup> + 1)}}
|-
! 4
| {{math|1=''x'' + 1}}
| {{math|1=0 = (''x'' + 1) &minus; 1 × (''x'' + 1)}}
| {{math|1=''x''<sup>6</sup> + ''x''<sup>4</sup> + ''x'' + 1 = (''x''<sup>4</sup>+''x''<sup>2</sup>) &minus; (''x''+1)(''x''<sup>5</sup>+''x''<sup>4</sup>+''x''<sup>3</sup>+''x''<sup>2</sup>+1)}}
|  
|}

Thus, the inverse is {{math|''x''<sup>7</sup> + ''x''<sup>6</sup> + ''x''<sup>3</sup> + ''x''}}, as can be confirmed by [[finite field arithmetic|multiplying the two elements together]], and taking the remainder by {{mvar|p}} of the result.