View source for Itoh-Tsujii inversion algorithm

The '''Itoh-Tsujii inversion algorithm''' is used to invert elements in a [[Finite field|finite field]].  It was introduced in 1988 and first used over GF(2<sup>''m''</sup>) using the [[Normal basis|normal basis]] representation of elements, however the algorithm is generic and can be used for other bases, such as the [[Polynomial basis|polynomial basis]].  It can also be used in any finite field, GF(''p''<sup>''m''</sup>).
The algorithm is as follows:
:'''Input''': ''A'' ∈ GF(''p''<sup>''m''</sup>)
:'''Output''': ''A''<sup>&minus;1</sup>
:#''r'' ← (''p''<sup>''m''</sup> &minus; 1)/(''p'' &minus; 1)
:#compute ''A''<sup>''r'' &minus; 1</sup> in GF(''p''<sup>''m''</sup>) 
:#compute ''A''<sup>''r''</sup> = ''A''<sup>''r'' &minus; 1</sup> · ''A''
:#compute (''A''<sup>''r''</sup>)<sup>&minus;1</sup> in GF(''p'')
:#compute ''A''<sup>&minus;1</sup> = (''A''<sup>''r''</sup>)<sup>&minus;1</sup> · ''A''<sup>''r'' &minus;1</sup>
:#return ''A''<sup>&minus;1</sup>

This algorithm is fast because steps 3 and 5 both involve operations in the subfield GF(''p'').  Similarly, if a small value of ''p'' is used a lookup table can be used for inversion in step 4.  The majority of time spent in this algorithm is in step 2, the first exponentiation.  This is one reason why this algorithm is well-suited for the normal basis, since squaring and exponentiation are relatively easy in that basis.

==References==
*T. Itoh and S. Tsujii. A Fast Algorithm for Computing Multiplicative Inverses in GF(2<sup>''m''</sup>) Using Normal Bases. ''Information and Computation'', 78:171-177, 1988.

<!-- ==External links==
*[http://www.win.tue.nl/~henkvt/ItohTsujiiEnciclopediaOfInfoSec-Submitted.pdf A thorough discussion of the Itoh-Tsujii algorithm by Guajardo] -->

[[Category:Finite fields]]
[[Category:Computational number theory]]

{{Sourceattribution|Itoh-Tsujii inversion algorithm|1}}