Prove that $x^{n}\pmod {(x^{4}+1)}=x^{n \pmod 4}$

Question

Assume $GF(2^k)[x]$ (where $k$ is a fixed natural number) is a ring of polynomials with coefficients in the field $GF(2^k)$. Prove that for every polynomial $x^n$ (where $n \in \mathbb{N}$) from $GF(2^k)[x]$ we have

$$x^{n}\pmod {(x^{4}+1)}=x^{n \pmod 4}$$

Any idea?

Thanks for your help.

Answer 1

That equality it's used in cryptography to speed up calculations in the ring $GF(2^k)[x]/(x^4+1)$.

$GF(2^8)$, $GF(2^8)[x]$ and $GF(2^8)[x]/(x^4+1)$ are essential algebraic structures used in Advanced Encryption Standard (AES). The elements of $GF(2^8)$ are represented in computers as 8-bit words, whereas the elements of $GF(2^8)[x]/(x^4+1)$ as 32-bit words.

Prove:

1. In $Z_2=\{0,1\}$, addition operation (denoted with "$\oplus$") is simply a sum modulo 2. Subtraction operation (denoted with "$\ominus$") is equivalent to addition. Because $1 \oplus 1 = 0$ and $0 \oplus 0 = 0$, so $-a=a$, ($a \in Z_2$), then $a \ominus b = a \oplus b$, ($a,b \in Z_2$).

2. In $GF(2^k)$, (whose elements are the words of binary length $k$), we define addition operation as the sum of polynomials. In our case, the sum of the coordinates modulo 2. If $a=(a_1, a_2, ..., a_k) \in GF(2^k)$, where $a_i \in \{0,1\}$ and $b=(b_1, b_2, ..., b_k) \in GF(2^k)$, where $b \in \{0,1\}$, then we have:

$$ a+b=(a_1 \oplus b_1, a_2 \oplus b_2, ..., a_k \oplus b_k)$$ $$ a-b=(a_1 \ominus b_1, a_2 \ominus b_2, ..., a_k \ominus b_k)=(a_1 \oplus b_1, a_2 \oplus b_2, ..., a_k \oplus b_k)$$

3. Of course, for $n<4$, the formula is true. For $n \ge 4$, there is a $q \in N$, that $n=q·4+r$ for $0 \le r \lt 4$, so $r=n \pmod 4$. Taking into account the point 2, we have:

and so indeed:

$$x^{n}\pmod {(x^{4}+1)}=x^{n \pmod 4}$$