I am not familiar with field theory so please bear with me if this is obvious to you. I actually have two questions:

  1. Why is addition and subtraction in GF(p^n) defined as:

    Addition and subtraction are performed by adding or subtracting two of these polynomials together, and reducing the result modulo the characteristic.

    Why modulo the characteristic p instead of p^n?

  2. Why does multiplication in GF(p^n) require an irreducible polynomial? (Why can't other polynomial work?)

  • $\begingroup$ The result of multiplication is reduced modulo an irreducible polynomial. You can multiply any two polynomials together. Your operations need to be well-defined. If you do multiplication modulo a reducible polynomial, you run into consistency problems. $\endgroup$ – Alvin Lepik Sep 28 '17 at 3:18

(1): I think "modulo the characteristic" here is a bit of a red herring. I will write $\mathbb{F}_p$ for the field with $p$ elements, where $p$ is a prime. You can think of each element in $\mathrm{GF}(p^n)$ as a polynomial with coefficients in $\mathbb{F}_p$, where the polynomial has degree less than $n$. All operations in $\mathrm{GF}(p^n)$ are just normal polynomial operations, but modulo some irreducible polynomial of degree $n$.

Forgetting about the modulo-the-irreducible part for the moment, computing in $\mathrm{GF}(2^n)$ should be just arithmetic using polynomials with coefficients in $\mathbb{F}_2$. For example:

$$\begin{aligned} (x^2 + 1)(x^3 + x + 1) + x &= x^5 + x^3 + x^2 + x^3 + x + 1 + x \\ &= x^5 + (1 + 1)x^3 + x^2 + (1 + 1)x + 1 \\ &= x^5 + x^2 + 1 \end{aligned}$$

The part where $(1 + 1) = 0$ is what the paragraph means by "reducing the result modulo the characteristic". The trick about $\mathrm{GF}(2^n)$ is that you then have to reduce this further using your chosen irreducible polynomial of degree $n$.

(2): If the polynomial you choose is not irreducible, the resulting system you end up with will not be a field. For example, let's suppose I take real polynomials modulo the reducible polynomial $x^2 -3x + 2 = (x-1)(x-2)$. Then the polynomial $x - 1$ is not zero, and $x - 2$ is not zero, but $(x-1)(x-2) \equiv 0 \pmod{x^2 - 3x + 2}$. So taking polynomials modulo a reducible polynomial does not leave us with a field.


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.