Inversion in $GF(2^{10})$ Using Composite Fields

Question

I'm designing a circuit that uses many $GF(2^{10})$ inverters. Normally for this sort of thing I use lookup tables. (Itoh-Tsujii is not efficient for these smaller fields.) This application is for an ASIC so the 1024-deep ROM will be optimized by the synthesizer. However, I recalled that when I built an AES encryptor, I used a Satoh S-box which efficiently computed the inverse in $GF(2^8)$ by splitting an element into two composite-field elements in $GF(2^4)$, performing an extended Euclidean algorithm which required finding an inverse in the much-smaller $GF(2^4)$, and then converting composite-field elements back to $GF(2^8)$.

The question is: could I do something similar to invert elements in $GF(2^{10})$ by using composite fields in $GF(2^5)$?

Answer 1

Do you know how to invert complex numbers? If yes, then you also know the answer to your question:

$$z^{-1} = \frac{\bar{z}}{z\cdot\bar{z}},$$

where $\bar{z}$ is the complex conjugate of $z$ (if $z=x+y\cdot i$ with $x, y\in\mathbb{R}$, then $\bar{z}=x-y\cdot i$) and $z\cdot\bar{z}=x^2+y^2\in\mathbb{R}$.

Complex conjugation is a field automorphism of order $2$, i.e., composed with itself it is the identity ($\bar{\bar{z}}=z$). For the field $\mathbb{F}_{2^{10}}$ squaring is a field automorphism (called Frobenius automorphism) of order $10$, as $z^{2^{10}} = z$ for $z\in\mathbb{F}_{2^{10}}$. So if you take the field automorphism $\sigma$ of $\mathbb{F}_{2^{10}}$ defined by $\sigma(z) = z^{32}$ (the 5th power of the Frobenius automorphism) you get an automorphism of order $2$ like for the complex numbers. The role of the real numbers (which are fixed under complex conjugation) is played by the field $\mathbb{F}_{32}$ (whose elements are fixed under $\sigma$).

If you know an irreducible polynomial $f$ of degree $5$ over $\mathbb{F}_2$, you can use it to define the field $\mathbb{F}_{32}$ as $\mathbb{F}_2[X]/(f(X))$. To get $\mathbb{F}_{2^{10}}$ as extension field of degree $2$ over $\mathbb{F}_{32}$ you can take the irreducible polynomial $g(T) = T^2+T+1$ over $\mathbb{F}_2$, which stays irreducible over $\mathbb{F}_{32}$ as $2$ does not divide $5$ ($\mathbb{F}_{32}$ doesn't have subfield of order $4$, as its order $32$ prevents it to be a vector space over $\mathbb{F}_4$): $\mathbb{F}_{2^{10}} = \mathbb{F}_{32}[T]/(g[T])$.

Any element $z\in\mathbb{F}_{2^{10}}$ you can write as $z = x+y\cdot T$, where for $T^2 = 1+T$ holds for $T\in\mathbb{F}_{2^{10}}$ (as $T$ is root of $g$). Now

$$z^{-1} = \frac{\sigma(z)}{z\cdot\sigma(z)} = \frac{\sigma(x+y\cdot T)}{(x+y\cdot T)\cdot\sigma(x+y\cdot T)} = \frac{x+y\cdot \sigma(T)}{(x+y\cdot T)\cdot(x+y\cdot\sigma(T)},$$ using that $x,y\in\mathbb{F}$ are fixed by $\sigma$. As $T^4 = (T^2)^2 = (T+1)^2 = T^2 + 1 = T + 1 + 1 = T$ ($T$ is in the subfield of order $4$ of $\mathbb{F}_{2^{10}}$) we get $\sigma(T) = ((T^4)^4)^2 = T^2 = T+1$ and therefore

$$z^{-1} = \frac{x+y\cdot(T+1)}{(x+y\cdot T)\cdot(x+y\cdot(T+1))} = \frac{x+y\cdot(T+1)}{x^2 + x\cdot y\cdot (T+1) + y\cdot T\cdot x + y\cdot T\cdot y\cdot(T+1)} = \frac{x+y\cdot(T+1)}{x^2 + x\cdot y + y^2},$$ using $T^2 + T = 1$.

The denominator is an element of $\mathbb{F}_{32}$, it's non-zero (do you know why?), so you can invert elements of $\mathbb{F}_{2^{10}}$ if you know how to invert elements of $\mathbb{F}_{32}$.