Itoh–Tsujii inversion algorithm: Difference between revisions

Revision as of 10:09, 10 January 2025

Latest revision as of 15:45, 19 January 2025

(7 intermediate revisions by one other user not shown)

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.

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

the [[normal basis]] representation of elements, however, it is generic and can be used for other bases,

such as the [[polynomial basis]]. It can also be used in any finite field {{math|GF(''p''^''m'')}}.

Line 30 ⟶ 24:

</math>

The above {{math|''A''^-1−1}} expression itself is close to that of the multiplicative Norm function in [[finite field]], which is defined as

<math display="block">

Norm(A)=\prod_{i=0}^{m-1}{A^{2^i}}.

Line 37 ⟶ 31:

This viewpoint leads us to consider the additive absolute Trace function

<ref>{{cite web |url=http://eprint.iacr.org/2020/482.pdf |title=A Trace Based {{math|GF(2^''n'')}} Inversion Algorithm

|access-date=Jan 10, 2025 |archive-url=http://eprint.iacr.org/2020/482 |first1=Haining|last1=Fan

|archive-date=May 6, 2020 }}</ref>

, which is defined as

Line 46 ⟶ 40:

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−1}} as

<math display="block">

A^{-1}=A^{-2}\sum_{i=1}^{m-1}{A^{2^i}}=\sum_{i=1}^{m-1}{A^{2^i-2}}=\sum_{j=0}^{m-2}{(A^2)^{2^{j}-1}}.

</math>

In some {{math|GF(2^''m'')}}s, for example, {{math|GF(2⁸)}} used in [[Advanced Encryption Standard]] (AES), this formula needs 1 less

multiplication operation than Feng and Itoh-Tsujii algorithm for elements with Trace value 0:

because

Line 68 ⟶ 62:

</math>

This additive formula needs 3 multiplications, 4 additions and 6 squarings.

But the multiplicative formula

Line 75 ⟶ 69:

</math>

needs 4 multiplications and 7 squarings.

== See also ==

Line 81 ⟶ 74:

* [[Finite field arithmetic]]

== References ==

{{reflist}}

* T. Itoh and S. Tsujii. A Fast Algorithm for Computing Multiplicative Inverses in GF(2^''m'') Using Normal Bases. ''Information and Computation'', 78:171–177, 1988.

<!-- ==External links==