Calculation in Rijndael field GF(2^8) and (mod x^4+1)?

I have a 6th degree polynomial with unknown coefficients, but I need to take it (mod x^4+1) to find some 3rd degree polynomial. Using wolfram alpha and mathematica 9.0, I could only reduce the polynomial to a different 6th degree polynomial that was shorter.


e.g. $\displaystyle a_1x^6 + a_2x^5 + ... a_6x + a_7$ is what I'm given, where each a_i is something like:
$\displaystyle a_1 = s_1 + s_3 + s_4$
$\displaystyle a_2 = s_1 + s_2 + s_3 $
$\displaystyle a_3 = s_3 + s_4$
...

for some unknown $\displaystyle s_i$.

Also, the coefficients are to (mod 2).

How can I find $\displaystyle a_1x^6 + a_2x^5 + ... a_6x + a_7$ (mod x^4+1) as a 3rd degree polynomial?

I heard that under mod (x^4 + 1) and (mod 2), I have congruence x^4 = -1 = 1 but that doesn't make sense to me?

Since x^4+1 = 0 mod (x^4+1), then x^4 = -1 mod (x^4+1).

Let me rewrite your 6th degree polynomial as:

f(x) = a6 * x^6 + a5 * x^5 + ...a1 * x + a0 = (a6,a5,a4,a3,a2,a1,a0) ...in other words concentrate on the coefficients.

Also note the subscript on the coefficient matches the power of x.

Now a4 * x^4 = a4 * (-1) mod (x^4+1). Likewise a5*x^5 = a5*(-x) and a6*x^6 = a6*(-x^2).

So (a6,a5,a4,a3,a2,a1,a0) = (a3,a2,a1,a0) - (a6,a5,a4) = (a3,a2-a6,a1-a5,a0-a4).

So the cubic is: a3 * x^3 + (a2-a6)*x^2 + (a1-a5)*x + (a0-a4).

If you want to work in GF(2^8), just take the coefficients mod (2^8).

Thanks a lot qmech! It's pretty obvious once you see how it's done...