While the algorithm is often called the Itoh-Tsujii algorithm, it was first presented by Feng.
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.
Feng and Itoh-Tsujii algorithm is first used to invert elements in
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
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 .
The algorithm is as follows:
: Input: ''A'' ∈ GF(''p''
''m'')
: Output: ''A''
−1
:# ''r'' ← (''p''
''m'' − 1)/(''p'' − 1)
:# compute ''A''
''r''−1 in GF(''p''
''m'')
:# compute ''A''
''r'' = ''A''
''r''−1 · ''A''
:# compute (''A''
''r'')
−1 in GF(''p'')
:# compute ''A''
−1 = (''A''
''r'')
−1 · ''A''
''r''−1
:# return ''A''
−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 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 is a cyclic group of order .
Given a nonzero element in
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
, we have
The above expression itself is close to that of the multiplicative Norm function in
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
, which is defined as
This viewpoint leads us to consider the additive absolute Trace function
, which is defined as
If =0, then we have
and can express as
In some s, for example, used in
Advanced Encryption Standard
The Advanced Encryption Standard (AES), also known by its original name Rijndael (), is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.
AES is a variant ...
(AES), this formula needs 1 less
multiplication operation than Feng and Itoh-Tsujii algorithm for elements with Trace value 0:
because
we have
and
This additive formula needs 3 multiplications, 4 additions and 6 squarings.
But the multiplicative formula
needs 4 multiplications and 7 squarings.
See also
*
Finite field arithmetic
In mathematics, finite field arithmetic is arithmetic in a finite field (a field containing a finite number of elements) contrary to arithmetic in a field with an infinite number of elements, like the field of rational numbers.
There are infinit ...
References
{{DEFAULTSORT:Itoh-Tsujii inversion algorithm
Finite fields
Computational number theory