Itoh–Tsujii inversion algorithm

Last updated January 20, 2025

While the algorithm is often called the Itoh-Tsujii algorithm, it was first presented by Feng.^[1] 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.^[2]

Feng and Itoh-Tsujii algorithm is first used to invert elements in finite field $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 $GF(p m)$ .

The algorithm is as follows:

Input: A ∈ GF(p^m)

Output: A⁻¹

r ← (p^m− 1)/(p− 1)
compute A^r−1 in GF(p^m)
compute A^r = A^r−1 · A
compute (A^r)⁻¹ in GF(p)
compute A⁻¹ = (A^r)⁻¹ · A^r−1
return A⁻¹

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 $GF(p m) *$ is a cyclic group of order $p m -1$ . Given a nonzero element $A$ in finite field $GF(2 m)$ , we have $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}}}.$

The above $A -1$ expression itself is close to that of the multiplicative Norm function in finite field, which is defined as $Norm(A)=\prod _{i=0}^{m-1}{A^{2^{i}}}.$

This viewpoint leads us to consider the additive absolute Trace function ^[3] , which is defined as $Tr(A)=\sum _{i=0}^{m-1}{A^{2^{i}}}.$

If $Tr (A)$ =0, then we have $A=\sum _{i=1}^{m-1}{A^{2^{i}}}$ and can express $A -1$ as $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}}.$

In some $GF(2 m)$ s, for example, $GF(2 8)$ 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 $0=Tr(A)=A+A^{2}+A^{4}+A^{8}+A^{16}+A^{32}+A^{64}+A^{128},$ we have $A=A^{2}+A^{4}+A^{8}+A^{16}+A^{32}+A^{64}+A^{128}$ and $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})^{8}A^{7}]\}^{2}.$

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

But the multiplicative formula $A^{-1}=A^{254}=A^{2}A^{4}A^{8}A^{16}A^{32}A^{64}A^{128}=\{A(A\cdot A^{2}A^{4})^{2}(A\cdot A^{2}A^{4})^{16}\}^{2}$ needs 4 multiplications and 7 squarings.

Related Research Articles

In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add.

In mathematics, a finite field or Galois field is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are the integers mod when $is a prime number.$

In mathematics, a geometric series is a series summing the terms of an infinite geometric sequence, in which the ratio of consecutive terms is constant. For example, the series is a geometric series with common ratio ⁠ $⁠$ , which converges to the sum of ⁠ $⁠$ . Each term in a geometric series is the geometric mean of the term before it and the term after it, in the same way that each term of an arithmetic series is the arithmetic mean of its neighbors.

A multiplication algorithm is an algorithm to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Numerous algorithms are known and there has been much research into the topic.

In mathematics, specifically in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The resulting matrix, known as the matrix product, has the number of rows of the first and the number of columns of the second matrix. The product of matrices $A$ and $B$ is denoted as $AB$ .

In modular arithmetic, a number $g$ is a primitive root modulo $n$ if every number $a$ coprime to $n$ is congruent to a power of $g$ modulo $n$ . That is, $g$ is a primitive root modulo $n$ if for every integer $a$ coprime to $n$ , there is some integer $k$ for which $g$ ^$k$ ≡ $a$ . Such a value $k$ is called the index or discrete logarithm of $a$ to the base $g$ modulo $n$ . So $g$ is a primitive root modulo $n$ if and only if $g$ is a generator of the multiplicative group of integers modulo $n$ .

In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. This has nothing to do with whether the function is one-to-one; finding any one input with the desired image is considered a successful inversion.

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

In mathematics, finite field arithmetic is arithmetic in a finite field contrary to arithmetic in a field with an infinite number of elements, like the field of rational numbers.

Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie–Hellman key exchange and RSA public/private keys.

In mathematics, an all one polynomial (AOP) is a polynomial in which all coefficients are one. Over the finite field of order two, conditions for the AOP to be irreducible are known, which allow this polynomial to be used to define efficient algorithms and circuits for multiplication in finite fields of characteristic two. The AOP is a 1-equally spaced polynomial.

KCDSA is a digital signature algorithm created by a team led by the Korea Internet & Security Agency (KISA). It is an ElGamal variant, similar to the Digital Signature Algorithm and GOST R 34.10-94. The standard algorithm is implemented over $, but an elliptic curve variant (EC-KCDSA) is also specified.$

The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers, published by Arnold Schönhage and Volker Strassen in 1971. It works by recursively applying fast Fourier transform (FFT) over the integers modulo $. The run-time bit complexity to multiply two n -digit numbers using the algorithm is in big O notation .$

In the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an explicit well-ordered set that represents the result of the operation or by using transfinite recursion. Cantor normal form provides a standardized way of writing ordinals. In addition to these usual ordinal operations, there are also the "natural" arithmetic of ordinals and the nimber operations.

In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer $a$ is an integer $x$ such that the product $ax$ is congruent to 1 with respect to the modulus $m$ . In the standard notation of modular arithmetic this congruence is written as

The block Wiedemann algorithm for computing kernel vectors of a matrix over a finite field is a generalization by Don Coppersmith of an algorithm due to Doug Wiedemann.

In theoretical computer science, the computational complexity of matrix multiplication dictates how quickly the operation of matrix multiplication can be performed. Matrix multiplication algorithms are a central subroutine in theoretical and numerical algorithms for numerical linear algebra and optimization, so finding the fastest algorithm for matrix multiplication is of major practical relevance.

The cyclotomic fast Fourier transform is a type of fast Fourier transform algorithm over finite fields. This algorithm first decomposes a DFT into several circular convolutions, and then derives the DFT results from the circular convolution results. When applied to a DFT over $, this algorithm has a very low multiplicative complexity. In practice, since there usually exist efficient algorithms for circular convolutions with specific lengths, this algorithm is very efficient.$

The carry-less product of two binary numbers is the result of carry-less multiplication of these numbers. This operation conceptually works like long multiplication except for the fact that the carry is discarded instead of applied to the more significant position. It can be used to model operations over finite fields, in particular multiplication of polynomials from GF(2)[X], the polynomial ring over GF(2).

In mathematics and computer science, polynomial evaluation refers to computation of the value of a polynomial when its indeterminates are substituted for some values. In other words, evaluating the polynomial $at consists of computing See also Polynomial ring § Polynomial evaluation$

References

↑ Feng, Gui-Liang (1989). "A VLSI architecture for fast inversion in $GF(2 m)$ ". IEEE Transactions on Computers . 38 (10): 1383–1386.
↑ Itoh, Toshiya; Tsujii, Shigeo (1988). "A fast algorithm for computing multiplicative inverses in $GF(2 m)$ ". Information and Computation . 78: 171–177.
↑ Fan, Haining. "A Trace Based $GF(2 n)$ Inversion Algorithm". Archived from the original (PDF) on May 6, 2020. Retrieved Jan 10, 2025.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Feng, Gui-Liang (1989). "A VLSI architecture for fast inversion in $GF(2 m)$ ". IEEE Transactions on Computers . 38 (10): 1383–1386.

[2] Itoh, Toshiya; Tsujii, Shigeo (1988). "A fast algorithm for computing multiplicative inverses in $GF(2 m)$ ". Information and Computation . 78: 171–177.

[3] Fan, Haining. "A Trace Based $GF(2 n)$ Inversion Algorithm". Archived from the original (PDF) on May 6, 2020. Retrieved Jan 10, 2025.

[1]

[2]

[3]