Itoh–Tsujii inversion algorithm: Difference between revisions

Revision as of 08:07, 23 April 2014

Latest revision as of 15:45, 19 January 2025

(21 intermediate revisions by 8 users not shown)

Line 1:

While the algorithm is often called the Itoh-Tsujii algorithm, it was first presented by Feng.<ref>{{cite journal |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>

The '''Itoh-Tsujii inversion algorithm''' is used to invert elements in a [[finite field]]. It was introduced in 1988 and first used over GF(2^''m'') using the [[normal basis]] representation of elements, however the algorithm is generic and can be used for other bases, such as the [[polynomial basis]]. It can also be used in any finite field, GF(''p''^''m'').

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>

Feng 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'')}}.

The algorithm is as follows:

: '''Input''': ''A'' ∈ GF(''p''^''m'')

: '''Output''': ''A''^&minus;1

:# ''r'' ← (''p''^''m'' &minus; 1)/(''p'' &minus; 1)

:# compute ''A''^{''r'' &minus; 1} in GF(''p''^''m'')

:# compute ''A''^''r'' = ''A''^{''r'' &minus; 1} · ''A''

:# compute (''A''^''r'')^&minus;1 in GF(''p'')

:# compute ''A''^&minus;1 = (''A''^''r'')^&minus;1 · ''A''^{''r'' &minus;1}

:# return ''A''^&minus;1

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 &nbsp;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.

This algorithm is based on the fact that {{math|GF(''p''^''m'')^*}} is a cyclic group of order {{math|''p''^''m''-1}}.

Given a nonzero element {{math|''A''}} in [[finite field]] {{math|GF(2^''m'')}}, we have

<math display="block">

A^{-1}=A^{2^m-2}=A^{2^{m-1}} \cdot A^{2^{m-2}} \cdot A^{2^{m-3}} \cdots A^{2^{2}} \cdot A^{2^{1}}=\prod_{i=1}^{m-1}{A^{2^i}}.

</math>

The above {{math|''A''⁻¹}} 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}}.

</math>

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

<math display="block">

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

</math>

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''⁻¹}} 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

<math display="block">

0=Tr(A)=A+A^2+A^4+A^8+A^{16}+A^{32}+A^{64}+A^{128},

</math>

we have

<math display="block">

A=A^2+A^4+A^8+A^{16}+A^{32}+A^{64}+A^{128}

</math>

and

<math display="block">

A^{-1}=1+A^2+A^6+A^{14}+A^{30}+A^{62}+A^{126}=1+ \{(A+A^3+A^7)+[(A+A^{3}+A^{7})^8A^7] \}^2.

</math>

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

But the multiplicative formula

<math display="block">

A^{-1}=A^{254}=A^2A^4A^8A^{16}A^{32}A^{64}A^{128}=\{ A(A \cdot A^2A^4)^2 (A \cdot A^2A^4)^{16} \}^2

</math>

needs 4 multiplications and 7 squarings.

== See also ==

* [[Finite field arithmetic]]

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

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

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

{{DEFAULTSORT:Itoh-Tsujii inversion algorithm}}

[[Category:Finite fields]]

[[Category:Computational number theory]]