Itoh–Tsujii inversion algorithm: Difference between revisions

Revision as of 10:20, 10 January 2025

Revision as of 10:44, 10 January 2025

Line 1:

While the algorithm is often called the Itoh-Tsujii algorithm, it was first presented by Feng <ref>{{cite journal |first=Gui-Liang |last=Feng |title=A {VLSI} architecture for fast inversion in {{math|GF(2^''m'')}}|journal=[[IEEE Transactions on Computers]] |volume=38 |issue=10 |pages=1383-1386 |date=1989 |first=Gui-Liang |last=Feng}}</ref>.

Feng's paper was received on March 13, 1987 and published in October 1989. Itoh and Tsujii's paper was received on July 8, 1987 and published in 1988 <ref>{{cite journal |journal=[[Information and Computation]]|volume=78 |pages=171-177 |date=1988 |first1=Toshiya |last1=Itoh|first2=Shigeo |last2=Tsujii |title=A fast algorithm for computing multiplicative inverses in {{math|GF(2^''m'')}} }}</ref>.

|journal=[[IEEE Transactions on Computers]] |volume=38 |issue=10 |pages=1383-1386 |date=Oct. 1989 } }</ref>. Feng's paper was received on March 13, 1987 and published in October 1989.

Itoh and Tsujii's paper

<ref>{{cite journal |first1=Toshiya |last1=Itoh|first2=Shigeo |last2=Tsujii

|title=A fast algorithm for computing multiplicative inverses in {{math|GF(2^''m'')}}

|journal=[[Information and Computation]]

|volume=78 |pages=171-177 |date=1988 } }</ref>

was received on July 8, 1987 and published in 1988.

This algorithm is first used to invert elements in [[finite field]] {{math|GF(2^''m'')}} using

Line 46 ⟶ 41:

If {{math|''Tr''(''A'')}}=0, then we have

<math display="block">

A=\sum_{i=1}^{m-1}{A^{2^i}}$

</math>

and can express {{math|''A''^-1}} as

Line 81 ⟶ 76:

* [[Finite field arithmetic]]

==References==

{{reflist}}

<!-- ==External links==