Itoh–Tsujii inversion algorithm

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 <a href="/facts/Finite_field/UkMGJo3m">finite field</a> GF(2m) using 
the <a href="/facts/Normal_basis/3bhymK7j">normal basis</a> representation of elements, however, it is generic and can be used for other bases, 
such as the <a href="/facts/Polynomial_basis/dcBE15Kq">polynomial basis</a>. It can also be used in any finite field GF(pm).
The algorithm is as follows:

Input: A ∈ GF(pm)
Output: A−1
<ol><li>r ← (pm − 1)/(p − 1)</li>
<li>compute Ar−1 in GF(pm)</li>
<li>compute Ar = Ar−1 · A</li>
<li>compute (Ar)−1 in GF(p)</li>
<li>compute A−1 = (Ar)−1 · Ar−1</li>
<li>return A−1</li></ol>
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(pm)* is a cyclic group of order pm-1.
Given a nonzero element A in <a href="/facts/Finite_field/UkMGJo3m">finite field</a> GF(2m), we have

A
          
            −
            1
          
        
        =
        
          A
          
            
              2
              
                m
              
            
            −
            2
          
        
        =
        
          A
          
            
              2
              
                m
                −
                1
              
            
          
        
        ⋅
        
          A
          
            
              2
              
                m
                −
                2
              
            
          
        
        ⋅
        
          A
          
            
              2
              
                m
                −
                3
              
            
          
        
        ⋯
        
          A
          
            
              2
              
                2
              
            
          
        
        ⋅
        
          A
          
            
              2
              
                1
              
            
          
        
        =
        
          ∏
          
            i
            =
            1
          
          
            m
            −
            1
          
        
        
          
            A
            
              
                2
                
                  i
                
              
            
          
        
        .
      
    
    {\displaystyle 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 <a href="/facts/Finite_field/UkMGJo3m">finite field</a>, which is defined as

N
        o
        r
        m
        (
        A
        )
        =
        
          ∏
          
            i
            =
            0
          
          
            m
            −
            1
          
        
        
          
            A
            
              
                2
                
                  i
                
              
            
          
        
        .
      
    
    {\displaystyle Norm(A)=\prod _{i=0}^{m-1}{A^{2^{i}}}.}

This viewpoint leads us to consider the additive absolute Trace function

, which is defined as

T
        r
        (
        A
        )
        =
        
          ∑
          
            i
            =
            0
          
          
            m
            −
            1
          
        
        
          
            A
            
              
                2
                
                  i
                
              
            
          
        
        .
      
    
    {\displaystyle Tr(A)=\sum _{i=0}^{m-1}{A^{2^{i}}}.}

If Tr(A)=0, then we have

A
        =
        
          ∑
          
            i
            =
            1
          
          
            m
            −
            1
          
        
        
          
            A
            
              
                2
                
                  i
                
              
            
          
        
      
    
    {\displaystyle A=\sum _{i=1}^{m-1}{A^{2^{i}}}}

and can express A−1 as

A
          
            −
            1
          
        
        =
        
          A
          
            −
            2
          
        
        
          ∑
          
            i
            =
            1
          
          
            m
            −
            1
          
        
        
          
            A
            
              
                2
                
                  i
                
              
            
          
        
        =
        
          ∑
          
            i
            =
            1
          
          
            m
            −
            1
          
        
        
          
            A
            
              
                2
                
                  i
                
              
              −
              2
            
          
        
        =
        
          ∑
          
            j
            =
            0
          
          
            m
            −
            2
          
        
        
          (
          
            A
            
              2
            
          
          
            )
            
              
                2
                
                  j
                
              
              −
              1
            
          
        
        .
      
    
    {\displaystyle 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(2m)s, for example, GF(28) used in <a href="/facts/Advanced_Encryption_Standard/HdXGBY2Q">Advanced Encryption Standard</a> (AES), this formula needs 1 less
multiplication operation than Feng and Itoh-Tsujii algorithm for elements with Trace value 0:
because

0
        =
        T
        r
        (
        A
        )
        =
        A
        +
        
          A
          
            2
          
        
        +
        
          A
          
            4
          
        
        +
        
          A
          
            8
          
        
        +
        
          A
          
            16
          
        
        +
        
          A
          
            32
          
        
        +
        
          A
          
            64
          
        
        +
        
          A
          
            128
          
        
        ,
      
    
    {\displaystyle 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
          
        
      
    
    {\displaystyle 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
          
        
        .
      
    
    {\displaystyle 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
        ⋅
        
          A
          
            2
          
        
        
          A
          
            4
          
        
        
          )
          
            2
          
        
        (
        A
        ⋅
        
          A
          
            2
          
        
        
          A
          
            4
          
        
        
          )
          
            16
          
        
        
          }
          
            2
          
        
      
    
    {\displaystyle 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.

Itoh–Tsujii inversion algorithm open-in-new

Itoh–Tsujii inversion algorithm