Itoh Tsuji algorithm I'd like to use the Itoh-Tsujii algorithm for a dynamic substitution table, but I do not get the following line:
$$r\ \gets\ (p^m - 1)\,/\,(p - 1)$$

And why can $r$ be used to calculate the multiplicative innverse of a number in a Galois field containing $p^m$ elements by calculating it in the field $GF(p)$ and use this result to calculate the inversion in the $GF(p^m)$ field?
I have recently detailed the use of Itoh-Tsuji in the article on Curve9767 (section 3.6).

In the description below, I write elements of $GF(p^m)$ as polynomials in $GF(p)[z]$, taken modulo a given irreducible unitary polynomial $M$ of degree $m$ (since all finite fields with the same cardinal are isomorphic to each other, the choice of a specific $M$ has no importance for security, but some choices of $M$ allow for better performance, as will be shown below). We consider the problem of computing the inverse $a^{-1}$ of a given element $a \in GF(p^m)$ (with $a \neq 0$).


$p^m-1$ is a multiple of $p-1$; in fact, the quotient is:
$$ r = \frac{p^m-1}{p-1} = 1 + p + p^2 + p^3 + \cdots + p^{m-1} $$
For any $a \in GF(p^m)$ distinct from zero, we can express the inverse of $a$ as:
$$ a^{-1} = \frac{a^{r-1}}{a^r} $$
This is true for any integer $r$, but for $r = (p^m-1)/(p-1)$, this leads to fast inversion thanks to two main facts, detailed below.
Fact 1: $a^r \in GF(p)$. Indeed, $(a^r)^{p-1} = a^{p^m-1} = 1$ (since $p^m-1$ is the order of the group of invertible elements in $GF(p^m)$). Thus, $a^r$ is a root of the polynomial equation $X^{p-1} - 1 = 0$. However, all non-zero elements of $GF(p)$ are roots of that polynomial (by Fermat's Little Theorem), and there are $p-1$ non-zero elements in $GF(p)$, and $X^{p-1} - 1$, being a polynomial of degree $p-1$ in a field, cannot have more than $p-1$ roots. Therefore, the roots of $X^{p-1}-1$ are exactly the non-zero elements of $GF(p)$, and $a^r$ is one of them.

This implies that inverting $a^r$ is much easier than inverting in general an element of $GF(p^m)$, since we can work in $GF(p)$. There are various methods for computing inverses modulo $p$, but if $p$ is small, Fermat's Little Theorem works well (i.e. raising $a^r$ to the power $p-2$).
Fact 2: computing $a^{r-1}$ is inexpensive, thanks to the Frobenius automorphism. The $j$-th Frobenius automorphism (for $j &gt;= 0$) is:
\begin{eqnarray*}
\Phi_j : GF(p^m) &amp;\longrightarrow&amp; GF(p^m) \\
a &amp;\longmapsto&amp; a^{p^j}
\end{eqnarray*}
i.e. $\Phi_1$ is just "raising to the power $p$", and $\Phi_j$ is "applying $\Phi_1$ exactly $j$ times".

This operator is a field automorphism: $\Phi_j(ab) = \Phi_j(a) \Phi_j(b)$ and $\Phi_j(a+b)$ = $\Phi_j(a) + \Phi_j(b)$ for all $a, b \in GF(p^m)$. This makes it linear (if we interpret $GF(p^m)$ as a vector space of dimension $m$ over $GF(p)$) and thus reasonably easy to compute: if:
$$ a = \sum_{i=0}^{m-1} a_i z^i $$
then:
$$ \Phi_j(x) = \sum_{i=0}^{m-1} a_i \Phi_j(z^i) $$
Moreover, if $GF(p^m)$ is defined with a modulus of the form $M = z^m - c$ for some constant $c \in GF(p)$ (there are constants $c$ that ensure that $z^m-c$ is irreducible, as long as $m$ divides $p-1$), then $\Phi_j(z^i) = c^{ij(p-1)/m}$, and applying $\Phi_j$ on any value $a$ becomes a matter of multiplying the $m$ coefficients $a_i$ of $a$ by $m$ constants that are easily precomputed. This makes $\Phi_j$ inexpensive (much cheaper than a single multiplication in $GF(p^m)$).

For any $a \in GF(p^m)$, we can compute $a^{r-1}$ by using a few multiplications and Frobenius operators:
\begin{eqnarray*}
t_1 &amp;=&amp; \Phi_1(a) &amp;=&amp; a^{p} \\
t_2 &amp;=&amp; t_1 \Phi_1(t_1) &amp;=&amp; a^{p+p^2} \\
t_3 &amp;=&amp; t_2 \Phi_2(t_2) &amp;=&amp; a^{p+p^2+p^3+p^4} \\
t_4 &amp;=&amp; t_3 \Phi_4(t_3) &amp;=&amp; a^{p+p^2+p^3+p^4+\cdots+p^{8}} \\
&amp; &amp; \ldots &amp; &amp;
\end{eqnarray*}
With about $\log m$ multiplications and applications of a Frobenius operator, one can obtain $a^{r-1}$.


Using all of the above, the complete inversion algorithm of $a \in GF(p^m)$ is then:


Using multiplications and the Frobenius operators, compute $a^{r-1}$.
Multiply $a$ by $a^{r-1}$ to get $a^r$ (this multiplication is made easy because we know that the result is in $GF(p)$, so we have only one coefficient to compute; the other ones are all zero).
Invert $a^r$ in $GF(p)$ (using for instance Fermat's Little Theorem).
Multiply $a^{r-1}$ by $a^{-r}$ (this multiplication is also easy, since $a^{-r} \in GF(p)$).


In Curve9767, which uses the field $GF(9767^{19})$, I can get the complete cost of the inversion down to about 6 to 7.7 times that of a multiplication in $GF(p^m)$, which is fast enough to seriously contemplate the use of affine coordinates for the operations on the elliptic curve. By comparison, usual algorithms for inversion modulo a 256-bit integer $n$ will take between 50 and 300 times the cost of a multiplication modulo $n$.



All of that is said in the generic context of $GF(p^m)$. Itoh and Tsuji first described it for $GF(2^m)$, i.e. with $p = 2$, in which case the Frobenius operator $\Phi_1$ is simply "squaring". Moreover, with $p = 2$, inversion in $GF(p)$ is a no-operation (since $GF(2)$ has only a single non-zero element, which is $1$, and $1$ is its own inverse), so $a^r = 1$; the inversion of $a^r$ and the multiplication by $a^{-r}$ can then be skipped. On the other hand, with $p = 2$, the modulus $M$ cannot be $z^m-c$ for some $c \in GF(2)$ because neither $X^m$ nor $X^m-1$ is irreducible over $GF(2)$, and you need an irreducible modulus to get a field. This makes the Frobenius operators somewhat more complex to compute (but still quite efficient).