msdousti's profile - activity

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$?

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.

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?

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$.

AES is a famous cipher. It has an operation called MixColumns (See Wikipedia entry Rijndael MixColumns) where operations take place over finite fields.

Actually, there's a specific polynomial $a(x) = a_3x^{3}+a_2x^{2}+a_1x+a_0$ whose coefficients belong to $GF(2^8)$. MixColumns is defined between $a(x)$ and any polynomial $b(x) = b_{3}x^{3}+b_{2}x^{2}+b_{1}x+b_{0}$ (whose coefficients belong to $GF(2^8)$ as well): It first multiplies $a(x)$ by $b(x)$ (where the algebraic rules between coefficients are governed by $GF(2^8)$), and then computes the remainder modulo $x^4 + 1$.

I tried to mimic the operations in Sage as follows:

R.<x> = PolynomialRing(GF(2), 'x')
S.<y> = QuotientRing(R, R.ideal(x^8+x^4+x^3+x+1))
T.<z> = QuotientRing(S, S.ideal(y^4+1))

But Sage displays an error on the last line. The error seems to be originating from the introduction of z. If I replace the last line with, say, T = QuotientRing(S, S.ideal(y^4+1)), the error goes away. Yet this is not what I intended.

Furthermore, the command S.ideal(y^4+1) outputs:

Principal ideal (1) of Univariate Quotient Polynomial Ring in y over Finite Field of size 2 with modulus x^8 + x^4 + x^3 + x + 1

I don't understand why its is the principal ideal (1) rather than the principal ideal (y^4+1).