Defining AES MixColumns in Sage

edit

Thanks a lot. Could you please answer the first part, too: ln short, how can I define $GF(256)[x] / \langle x^4 + 1 \rangle$ in Sage? I mean, as stated in the question, addition and multiplication of polynomials with coefficients in $GF(256)$ modulo $x^4+1$.

I tried to be clearer.

Thanks again. Let me just confirm my understanding: Sage does not provide a way for defining $GF(256)[x] / \langle x^4 + 1 \rangle$, right?

What's wrong with

sage: R.<x> = PolynomialRing(GF(256), 'x')
sage: R.quotient(x^4 + 1)
Univariate Quotient Polynomial Ring in xbar over Finite Field in z8 of size 2^8 with modulus x^4 + 1

It must work, but it does not (to my surprise). In your definition, $R$ is the ring of polynomials with coefficients over $GF(256)$, but sage treats it as the ring of polynomials with coefficients over $GF(2)$! Just enter something like 5*x in sage, and it interprets this polynomial as x. Or enter x+x, and sage outputs 0.

In GF(256) we have 5*x = x. What does mean 5 in GF(256) for you? If you want some polynomial whose coefficients are not 0 or 1 you can do

sage: K = GF(256)
sage: R.<x> = K[]
sage: K.fetch_int(15) * x^2 + K.fetch_int(105) * x + K.fetch_int(75)
(z8^3 + z8^2 + z8 + 1)*x^2 + (z8^6 + z8^5 + z8^3 + 1)*x + z8^6 + z8^3 + z8 + 1

or

sage: z = K.gen()
sage: (z^13 + 1) * x^2 + (z^8 + z^2 + 1) * x + z + 1
(z8^7 + z8^2 + z8)*x^2 + (z8^4 + z8^3)*x + z8 + 1

Yes, in $GF(256)$ we have 5*x = x. But I want to define a polynomial in $GF(256)[x]$, which is a polynomial whose coefficients belong to $GF(256)$, not one whose coefficients belong to $GF(2)$. Actually, as I pointed in a few comments above, I'd like to define the polynomial ring $GF(256)[x] / \langle x^4 + 1 \rangle$. The last approach you suggested seems very promising. Can you further hint on how to generalize it for the polynomial ring $GF(256)[x] / \langle x^4 + 1 \rangle$?