For multiplications over a finite field, what happens to the elements which, after modulo the reducing polynomial, still don't fit in the field?

Question

To the best of my understanding, performing multiplication over finite-field elements looks like:

1. Multiply the elements together in their polynomial representation; and then
2. if the resulting polynomial is too large to fit in the group, take the remainder upon dividing by some reducing polynomial.

For example, for GCM-AES we do multiplications over $\text{GF}(2^{128})$ with reducing polynomial $x^{128} + x^7 + x^2 + x + 1$. However, the largest polynomial that could exist in $\text{GF}(2^{128})$ is $x^{127} + x^{126} + x^{125} + ... + x^2 + x + 1$. Then, my problem is that there are some polynomials that fit 'in between' the largest field element and the reducing polynomial, so there are some cases for multiplication that wouldn't end up resulting in field elements. I am sure this is somehow avoided, but I don't see immediately how.

How do we treat the result of multiplication if, after modulo the reducing polynomial, the result is still larger than the largest group element?

---

EDIT: To pose an example, one such element might be $x^{128} + x^7 + x^2 + x$, so one short of the modulus. This means that the number produced by the 'initial' step of the multiplication would have been $p(x) \cdot \left( x^{128} + x^7 + x^2 + x + 1 \right) + x^{128} + x^7 + x^2 + x$.

Taking the simplest case of $p(x) = 1$ would give (what seems to me to be, anyway) a nonsense result because the $x^{128}$ terms cancel and we get a result well within the field.

Taking instead $p(x) = x$ means that the result of the multiplication would have been $x^{129} + x^{128} + x^8 + x^7 + x^3$. This can then be factored into $x^3 \cdot \left(x^{126} + x^{125} + x^5 + x^4 + 1 \right)$, both of which are now field elements, but which, by my maths above, seem to multiply to give an element which ends up 'outside' the field after taking the remainder with respect to the reducing polynomial. So, how is this resolved?

My apologies in advance if I've made an arithmetic error, but I hope this example at least makes clear what I'm trying to get at, that there seems to be some 'space' between the number of field elements and the number of polynomials that exist modulo the reducing polynomials, and that I don't know how to deal with these. Thanks!

Answer 1

Let $m(x) = x^{128} + x^7 + x^2 + x +1$, the "reducing polynomial". In the field $K = \mathbb{Z}[x]/m(x)$ that polynomial represents $0$. So $$ f(x) = x^{128} + x^7 + x^2 + x = m(x) -1 $$ is just $-1$ in $K$.

Another way to say this is that when you divide $f(x)$ by $m(x)$ the quotient is $1$ and the remainder is $-1$, which is just $1$ in characteristic $2$.

Answer 2

My educated guess (supported by the reaction to my comments) is that the confusion arises from the following.

It is a common trick to store and represent elements of $GF(2^m)=GF(2)[x]/\langle f(x)\rangle$, where $f(x)=x^m+\sum_{i=0}^{m-1}a_ix^i$ as a string of $m$ bits. Basically, the coset of $b(x)=\sum_{i=0}^{m-1}b_ix^i$ then becomes the bit string $$ b(x)+\langle f(x)\rangle= b_{m-1}b_{m-2}\cdots b_1b_0, $$ and the elements of $GF(2^m)$ are then exactly all the strings of $m$ bits.

This is a very useful programming trick. For example the addition in $GF(2^m)$ then becomes a simple bitwise XOR of the corresponding bit strings.

A recurring source of questions (and confusion) on our site is that programmers are used to think of bit strings as integers. After all, the same string of bits also represents the integer $$ b(2)=\sum_{i=0}^{m-1}b_i2^i\in\Bbb{Z}. $$ For $b(2)$ to make sense we need to first convert the coefficients $b_i$ of the polynomial $b(x)$ to ordinary integers $0$ and $1$ as opposed to being elements of $GF(2)$.

The confusion starts when:

• either the programmers take the integer interpretation too seriously, and try and apply rules of integer arithmetic to a problem, or
• users well versed in algebra take that $b(2)$ is an integer-interpretation too literally.

---

The current OP seems to be confused about the following. They have similarly converted the defining polynomial $f(x)$ into the integer $f(2)$, having $(m+1)$ bits due to the presences of the $x^m$-term. This is actually fine. For example, I have often seen the AES/Rijndael defining polynomial of $GF(2^8)$, $$f(x)=x^8+x^4+x^3+x+1$$ interpreted as an integer becomes $$ f(2)=10001101_2=283_{10}. $$

When calculating the product of two elements of $GF(2^m)$ using this representation of the elements, the programmers need to implement two steps:

1. the (carryless) multiplication of the $b$-polynomials, and
2. a reduction modulo $f(x)$ step.

When performing ordinary arithmetic with integers modulo $m$, it is not unnatural to think of numbers in the range $0\ldots m-1$ as being reduced. After all, further subtracting multiples of $m$ makes the remainder negative, which is often frowned upon.

When doing modular arithmetic modulo the defining polynomial $f(x)$, or $f(2)$, the rule is different. A "number" in $GF(2^m)$ is not fully reduced, if any of its bits in positions $m$ or higher is ON. The difference comes from the fact that instead of subtracting $f(2)$, this time we are bitwise XOR with $f(2)$ (or its shifted versions $2^if(2)$ when we need to make the bit at position $m+i$ to zero).

For example in the AES field the element $$ 100000111_2=263_{10} $$ appears to be below the modulus $f(2)=283_{10}$, but it is not yet fully reduced modulo $f(x)$ because its bit $b_8=1$. The remedy is to calculate the bitwise XOR $$ 263\hat{}283=100000111\hat{}100011011=00011100_2=28_{10}. $$ This bit string fits into $8$ bits, and can be thought of as being fully reduced.