Editing Finite field arithmetic (section)

==Multiplicative inverse==
{{See also|Itoh–Tsujii inversion algorithm}}

The [[multiplicative inverse]] for an element '''a''' of a finite field can be calculated a number of different ways:

* By multiplying '''a''' by every number in the field until the product is one. This is a [[brute-force search]].
* Since the nonzero elements of GF(''p<sup>n</sup>'') form a [[finite group]] with respect to multiplication, {{nowrap|1=''a''{{i sup|''p<sup>n</sup>''−1}} = 1}} (for {{nowrap|''a'' ≠ 0}}),  thus the inverse of ''a'' is ''a''{{i sup|''p<sup>n</sup>''−2}}. This algorithm is a generalization of the [[modular multiplicative inverse]] based on  [[Fermat's little theorem]].
* Multiplicative inverse based on the [[Fermat's little theorem]] can also be interpreted using the multiplicative Norm function in [[finite field]]. This new viewpoint leads to an inverse algorithm based on the additive Trace function in [[finite field]].<ref>{{cite web |url=http://eprint.iacr.org/2020/482.pdf |title=A Trace Based {{math|GF(2<sup>''n''</sup>)}} Inversion Algorithm |first1=Haining|last1=Fan
|access-date=Jan 10, 2025 |archive-url=http://eprint.iacr.org/2020/482
|archive-date=May 6, 2020 }}</ref>
* By using the [[extended Euclidean algorithm]].
* By making [[logarithm]] and [[exponentiation]] tables for the finite field, subtracting the logarithm from ''p<sup>n</sup>''&nbsp;−&nbsp;1 and exponentiating the result.
* By making a [[modular multiplicative inverse]] table for the finite field and doing a lookup.
* By mapping to a [[Finite field arithmetic#Composite field|composite field]] where inversion is simpler, and mapping back.
* By constructing a special integer (in case of a finite field of a prime order) or a special polynomial (in case of a finite field of a non-prime order) and dividing it by ''a''.<ref>{{citation|last1=Grošek|first1= O.|last2=Fabšič|first2= T.|year= 2018|title= Computing multiplicative inverses in finite fields by long division|journal= Journal of Electrical Engineering|volume= 69|issue=5|pages=400–402|url= https://www.degruyter.com/downloadpdf/j/jee.2018.69.issue-5/jee-2018-0059/jee-2018-0059.pdf|doi=10.2478/jee-2018-0059|s2cid= 115440420|doi-access= free|bibcode= 2018JEE....69..400G}}</ref>