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?