Factorization and GCD for Rijndael's finite field

Question

I'm factoring polynomials in $GF(2^8)$ with modulo polynomial $m = 2^8 + 2^4 + 2^3 + 2^1 + 2^0$

In particular, I factored

a = 0x49 = $$2^6 + 2^3 + 2^0 = 2^1 * (2^1 + 2^0)^6 * (2^2 + 2^1 + 2^0) * (2^4 + 2^1 + 2^0) * (2^3 + 2^1 + 2^0) \bmod{m}$$

b = 0x64 = $$2^6 + 2^5 + 2^2 = (2^1)^3 * (2^1 + 2^0) * (2^3 + 2^1 + 2^0) * (2^3 + 2^2 + 2^0) \bmod{m}$$

these numbers are multiplicative inverses and I can calculate directly using long division that $ab\bmod{m} = 2^0$.

I assume GCD should also be $1$, i.e. $2^0$.

Now I want to calculate GCD using just factored irreducible polynomials.

I know that for integers GCD equals the product of prime numbers (including their powers) present in both factorization, does it still hold here?

$gcd = 2^1 * (2^1 + 2^0) * (2^3 + 2^1 + 2^0) \bmod{m} = 2^5 + 2^4 + 2^3 + 2^1$

Can anyone please tell me where I am mistaken?

Thank you!

Answer 1

A fundamental problem is that while there are primes in the ring of polynomials $GF(2)[x]$ (where you can also run the (extended) Euclidean algorithm, there are no primes in the field $GF(2^8)=GF(2)[x]/\langle m(x)\rangle$. The same holds in all fields. Technically, all the non-zero elements of a field are units, and hence divisible by each other.

This manifests in many ways (reverting to the notation that $2^k$ is the residue class of $x^k$ modulo $m(x)$):

• Because $ab=2^0$ the element $b$ divides all the "factors" you listed. For example $2^3+2^1+2^0=ab(2^3+2^1+2^0)$ is clearly "divisible" by $b$. Q: Which one of $b$ and $2^3+2^1+2^0$ is a factor of the other? A: Both!
• Because $2^8+2^4=2^4(2^4+2^0)=(2^1)^4(2^1+2^0)^4$, and also $2^8+2^4=2^3+2^1+2^0$ (in $GF(2^8)$ "=" means the same thing as congruent modulo $m$), we see that $$2^3+2^1+2^0=(2^1+2^0)^4(2^1)^4.$$ Therefore the factor $2^3+2^1+2^0$ is not a "prime" either.
• For some reason unknown to me here a non-primitive polynomial $m(x)$ is used in defining the field (I erred here initially in one of the comments). Anyway a computer check reveals that $x^{51}\equiv 1\pmod {m(x)}$, and that $51$ is the smallest positive exponent when this happens. Therefore the powers of $2^1$ cover one fifth of the elements of $GF(256)$. Another computer check reveals that $2^1+2^0$ is not among those $51$. But, again by computer, we do have the relation $$(2^1+2^0)^5=(2^1)^{42}=(2^1)^{-9}.$$ This implies that any element $z\in GF(2^8), z\neq0,$ can be written uniquely in the form $$z=(2^1)^k*(2^1+2^0)^\ell,$$ with $0\le k<51$, $0\le \ell<5$.
• Therefore you never need "primes" other than $2^1+2^0$ and $2^1$. And these two are also "divisible" by each other.

It may be useful to look at the analogy of the residue class ring $\Bbb{Z}_{17}$ of integers modulo the prime $17$:

• We have $2^4=-1$ in this ring, and therefore also $2^8=1$, so do we really want to call $2$ a "prime". It is a factor of $1$ after all!
• We have $3=20=2^2\cdot5$, so $3$ is not a "prime" but it doesn't really make sense to call $2^2\cdot 5$ a factorization of $3$ into "primes" either.
• Similarly $5^2=25=8=2^3$, and therefore also $5^6=(2^3)^3=2^9=2^8\cdot 2=2$. Actually all the non-zero element of $\Bbb{Z}_{17}$ are powers of $5$. But also $5=-12=-2^2\cdot3$ is "divisible" by both $2$ and $3$.

The analogy I wanted to make in comparing $GF(2^8)$ and $\Bbb{Z}_{17}$ is that when working in $GF(2^8)$ we may occasionally benefit from working inside the polynomial ring $GF(2)[x]$ where we have things like the extended Euclidean algoritm. Similarly in $\Bbb{Z}$ we have the extended Euclidean algorithm allowing us to calculate inverses in $\Bbb{Z}_{17}$. But, talking about primes in $GF(2^8)$ is equally futile as talking about primes in $\Bbb{Z}_{17}$.

I'm afraid that...

To clear up all the fog it may be necessary to read an introductory level textbook on abstract algebra.