9
$\begingroup$

The binary extension field, usually denoted as $\textsf{GF}(2^n)$ or $\mathbb{F}_{2^n}$, is a finite field of characteristic 2.

Are there any applications of $\textsf{GF}(2^n)$ (or more broadly, $\textsf{GF}(p^n)$), for $n>1$, in computer science?

My impression is that most applications only require a sufficiently large domain. Therefore $\textsf{GF}(p)$ suffices. One exception is in cryptography: the design of some popular block ciphers uses binary extension fields. But more recent cryptographic designs seem to avoid $\textsf{GF}(2^n)$ operations.

$\endgroup$

2 Answers 2

14
$\begingroup$

$GF(2^n)$ is used in error correcting codes, in some elements of cryptography (e.g., message authentication with 2-universal hashing), and in the AES block cipher, which is very widely used.

$\endgroup$
4
$\begingroup$

There indeed aren't a lot of situations where any binary extension field would work but no other finite field would. In fact, I can't think of any off the top of my head. Usually, you either need a specific field (and often a specific representation of that field, as with AES) or you just need a finite field and any one of sufficient size can (at least theoretically) be used.

That said, in cases where any (sufficiently large) finite field would do, binary extension fields are often a convenient choice due to the fact that their elements map 1:1 to fixed-length bitstrings.

This makes converting binary data (which is what our computers store everything as) into field elements and back very easy and convenient, since you don't really have to do anything — you can just take any string of $n$ bits and say that it represents an element of $GF(2^n)$!


For example, Shamir's threshold secret sharing scheme was originally formulated over prime fields, but it works over any finite field. For computer implementation binary extension fields are usually preferred, with the most convenient choice often being $GF(2^8)$, since it allows you to share arbitrary byte sequences and keep the byte length of the shares equal to that of the secret string.

(The only major drawback of using $GF(2^8)$ is that it only allows at most 255 shares, since each share needs to be associated with a unique non-zero field element. Of course, if that's a problem, you can use $GF(2^{16})$ or $GF(2^{32})$ or even $GF(2^{256})$ instead and pad your secret with some extra bytes as needed.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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