3
$\begingroup$

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)$?

$\endgroup$
  • 1
    $\begingroup$ I think the arrangement is not as elegant as with $GF(2^8)$ because $GF(2^5)$ has no non-trivial subfields. You will be stuck inverting an element of $GF(2^5)$. $\endgroup$ – conchild Mar 20 at 20:34
  • 1
    $\begingroup$ I'd rather invert a $GF(2^5)$ element, which could be done with a 5 x 32 lookup table, rather than a 10 x 1024 lookup table. $\endgroup$ – Evariste Mar 21 at 0:48
3
$\begingroup$

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}$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks kindly for your answer. I'm slowly parsing it. Hopefully I can even use it in my circuit design... $\endgroup$ – Evariste Mar 23 at 17:07
  • $\begingroup$ @Evariste: How do you represent your elements of your field with 1024 elements? With a primitive polynomial of degree 10? Probably you'll need to identify the subfield of order 32 and a root of $X^2+X+1$, and use them to find a linear (over the field with 2 elements) transformation for converting between your and my representation. It might be more efficient if you can keep your values always in my representation as pairs of elements of the field with 32 elements. $\endgroup$ – j.p. Mar 24 at 7:29
  • $\begingroup$ I have to figure out how to convert between the fields. Unfortunately at work I was pulled into working on more mundane things at the moment. I'm using a polynomial representation of the $GF(2^{10})$ elements with the field polynomial of $x^{10}+x^3+1$. $\endgroup$ – Evariste Mar 24 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.