I am currently reading a paper Cryptanalysis of a Theorem Decomposing the Only Known Solution to the Big APN Problem. In this paper, they mention that they used $I$ which is the inverse of the finite field GF($2^3$) with the irreducible polynomial $x^3 + x + 1$. This inverse corresponds to the monomial $x \mapsto x^6$. Can anyone tell me how this inverse function of the finite field was defined? I understand that there are multiplicative inverses of elements in the finite fields. Are these two the same thing?

How can the inverse function of the finite field GF($2^4$) be derived?


Yes, the only sensible interpretation I can see is that they're talking about the multiplicative inverse.

In particular, the multiplicative group of a finite field is cyclic, and contains all the non-zero elements of the field. This implies that its order is the size of the field minus one, i.e. $2^3 - 1 = 7$ for ${\rm GF}(2^3)$, and thus that $a^6 \cdot a = a^7 = 1$ for all $a \in {\rm GF}(2^3)$, which means that $a^6$ is the multiplicative inverse of $a$.

Similarly, the multiplicative group of ${\rm GF}(2^4)$ has $2^4 - 1 = 15$ elements, and thus the multiplicative inverse of any non-zero element $a \in {\rm GF}(2^4)$ can be calculated as $2^{14}$. More generally, in any Galois field ${\rm GF}(p^n)$, the multiplicative inverse of $a$ equals $a^{p^n-2}$.

A point of notation perhaps worth making here is that by $a^6$ above I mean the field element $a$ raised to the sixth power using the field multiplication rule — which itself can be represented as polynomial multiplication followed by reduction modulo an irreducible monic polynomial, if the elements of ${\rm GF}(2^3)$ themselves are represented as polynomials over ${\rm GF}(2)$ of order less than 3.

The reason this can be confusing is that, in this representation, expressions like "$x$" and "$x^6$" could themselves represent specific field elements, written as polynomials of a single variable $x$. (Of course, $x^6$ cannot be the canonical polynomial representation of any element of ${\rm GF}(2^3)$, since its order is too high.) Where such notation is used, as in your question, it's usually a good idea to avoid using the symbol $x$ for any other purpose except as the formal variable in the polynomials representing the field elements. In particular, it should not be used to designate an arbitrary field element (except, of course, for the specific field element canonically represented by the first order monomial $x$).


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.