Editing Extended Euclidean algorithm (section)

==Computing multiplicative inverses in modular structures==

The extended Euclidean algorithm is the essential tool for computing [[multiplicative inverse]]s in modular structures, typically the [[modular arithmetic|modular integer]]s and the [[algebraic field extension]]s. A notable instance of the latter case are the finite fields of non-prime order.

===Modular integers===
{{main|Modular arithmetic}}
If {{math|''n''}} is a positive integer, the [[Ring_(mathematics)|ring]] {{math|[[Z/nZ|'''Z'''/''n'''''Z''']]}} may be identified with the set {{math|{0, 1, ..., ''n''-1}{{void}}}} of the remainders of [[Euclidean division]] by {{math|''n''}}, the addition  and the multiplication consisting in taking the remainder by {{math|''n''}} of the result of the addition and the multiplication of integers. An element {{math|''a''}} of {{math|'''Z'''/''n'''''Z'''}} has a multiplicative inverse (that is, it is a [[unit (ring theory)|unit]]) if it is [[coprime]] to {{math|''n''}}. In particular, if {{math|''n''}} is [[prime number|prime]], {{math|''a''}} has a multiplicative inverse if it is not zero (modulo {{math|''n''}}). Thus {{math|'''Z'''/''n'''''Z'''}} is a field if and only if {{math|''n''}} is prime.

Bézout's identity asserts that {{math|''a''}} and {{math|''n''}} are coprime if and only if there exist integers {{math|''s''}} and {{math|''t''}} such that 
:<math>ns+at=1</math>
Reducing this identity modulo {{math|''n''}} gives 
:<math>at \equiv 1 \mod n.</math>
Thus {{math|''t''}}, or, more exactly, the remainder of the division of {{math|''t''}} by {{math|''n''}}, is the multiplicative inverse of {{math|''a''}} modulo {{math|''n''}}.

To adapt the extended Euclidean algorithm to this problem, one should remark that the Bézout coefficient of {{math|''n''}} is not needed, and thus does not need to be computed. Also, for getting a result which is positive and lower than ''n'', one may use the fact that the integer {{math|''t''}} provided by the algorithm satisfies {{math|{{!}}''t''{{!}} < ''n''}}. That is, if {{math|''t'' < 0}}, one must add {{math|''n''}} to it at the end. This results in the [[pseudocode]], in which the input ''n'' is an integer larger than 1.
 '''function''' inverse(a, n)
     t := 0;     newt := 1
     r := n;     newr := a
 
     '''while''' newr ≠ 0 '''do'''
         quotient := r '''div''' newr
         (t, newt) := (newt, t − quotient × newt) 
         (r, newr) := (newr, r − quotient × newr)
 
     '''if''' r > 1 '''then'''
         '''return''' "a is not invertible"
     '''if''' t < 0 '''then'''
         t := t + n
 
     '''return''' t

=== 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.