Ask Your Question

# Revision history [back]

### How to express unknown coefficients in GF(2^8)?

I want to make computations in GF(2^8) using the Rijndael modulus X^8+X^4+X^3+X+1 and with unknown elements of GF(2^8).

For example, I need a polynomial x which is defined as x = x_7 * X^7 + x_6 * X^6 + x_5 * X^7 + ... + x_0

x.coefficients() should return [x_0, x_1, x_2, x_3, x_4, ...]

If I for example add x to y, I would expect that the result would be a term like (x_7+y_7) * X^7 + (x_6+y_6)*X^6 + ...

I tried the following:

sage: pgen = polygen(Integers(2))
sage: modulus = pgen()**8 + pgen()**4 + pgen()**3 + pgen() + 1
sage: F = FiniteField(2**8, 'X', modulus = modulus)
sage: X = F.gen()
X
sage: x_coeffs = list(var('x_%d' % i) for i in range(8))
sage: y_coeffs = list(var('y_%d' % i) for i in range(8))
sage: uF = PolynomialRing(F, 16, x_coeffs + y_coeffs); uF
Multivariate Polynomial Ring in x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, y_0, y_1, y_2, y_3, y_4, y_5, y_6, y_7 over Finite Field in a of size 2^8

sage: poly_x = uF(x_0 * X^0 + x_1 * X^1 + x_2 * X^2 + x_3 * X^3 + x_4 * X^4 + x_5 * X^5 + x_6 * X^6 + x_7 * X^7)
sage: poly_y = F(y_0 * X^0 + y_1 * X^1 + y_2 * X^2 + y_3 * X^3 + y_4 * X^4 + y_5 * X^5 + y_6 * X^6 + y_7 * X^7)


But the coefficients of poly_x and poly_y are not the variables x_0, x_1 etc. but the X^0, X^1, etc...

I also tried:

sage: F = GF(2^8, 'X')
sage: X = F.gen()
X
sage: x_coeffs = list(var('x_%d' % i) for i in range(8))
sage: y_coeffs = list(var('y_%d' % i) for i in range(8))
sage: poly_x = 0*X
sage: type(poly_x)
<type 'sage.rings.finite_rings.element_givaro.FiniteField_givaroElement'>
sage: for i in xrange(8):
....:     poly_x += x_coeffs[i] * X^i
....:
sage: poly_x
x_0 + X*x_1 + X^2*x_2 + X^3*x_3 + X^4*x_4 + X^5*x_5 + X^6*x_6 + X^7*x_7
sage: type(poly_x)
<type 'sage.symbolic.expression.Expression'>
sage: poly_x.coefficients()
[[X*x_1 + X^2*x_2 + X^3*x_3 + X^4*x_4 + X^5*x_5 + X^6*x_6 + X^7*x_7, 0],
[1, 1]]


which is also not what I want. Also, expressions like the follow lead to an error:

sage: F(x_1*X)
TypeError: unable to coerce <type 'sage.symbolic.expression.Expression'>


How can I express unknown elements with unknown coefficients?

### How to express unknown coefficients in GF(2^8)?

I want to make computations in GF(2^8) using the Rijndael modulus X^8+X^4+X^3+X+1 and with unknown elements of GF(2^8).

For example, I need a polynomial x which is defined as x = x_7 * X^7 + x_6 * X^6 + x_5 * X^7 + ... + x_0

x.coefficients() should return [x_0, x_1, x_2, x_3, x_4, ...]

If I for example add x to y, I would expect that the result would be a term like (x_7+y_7) * X^7 + (x_6+y_6)*X^6 + ...

I tried the following:

sage: pgen = polygen(Integers(2))
sage: modulus = pgen()**8 + pgen()**4 + pgen()**3 + pgen() + 1
sage: F = FiniteField(2**8, 'X', modulus = modulus)
sage: X = F.gen()
X
sage: x_coeffs = list(var('x_%d' % i) for i in range(8))
sage: y_coeffs = list(var('y_%d' % i) for i in range(8))
sage: uF = PolynomialRing(F, 16, x_coeffs + y_coeffs); uF
Multivariate Polynomial Ring in x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, y_0, y_1, y_2, y_3, y_4, y_5, y_6, y_7 over Finite Field in a of size 2^8

sage: poly_x = uF(x_0 * X^0 + x_1 * X^1 + x_2 * X^2 + x_3 * X^3 + x_4 * X^4 + x_5 * X^5 + x_6 * X^6 + x_7 * X^7)
sage: poly_y = F(y_0 * X^0 + y_1 * X^1 + y_2 * X^2 + y_3 * X^3 + y_4 * X^4 + y_5 * X^5 + y_6 * X^6 + y_7 * X^7)


(which is very much like I found it in the sources of sage.crypto.mq.rijndael_gf.RijndaelGF)

But the coefficients of poly_x and poly_y are not the variables x_0, x_1 etc. but the X^0, X^1, etc...

I also tried:

sage: F = GF(2^8, 'X')
sage: X = F.gen()
X
sage: x_coeffs = list(var('x_%d' % i) for i in range(8))
sage: y_coeffs = list(var('y_%d' % i) for i in range(8))
sage: poly_x = 0*X
sage: type(poly_x)
<type 'sage.rings.finite_rings.element_givaro.FiniteField_givaroElement'>
sage: for i in xrange(8):
....:     poly_x += x_coeffs[i] * X^i
....:
sage: poly_x
x_0 + X*x_1 + X^2*x_2 + X^3*x_3 + X^4*x_4 + X^5*x_5 + X^6*x_6 + X^7*x_7
sage: type(poly_x)
<type 'sage.symbolic.expression.Expression'>
sage: poly_x.coefficients()
[[X*x_1 + X^2*x_2 + X^3*x_3 + X^4*x_4 + X^5*x_5 + X^6*x_6 + X^7*x_7, 0],
[1, 1]]


which is also not what I want. Also, expressions like the follow lead to an error:

sage: F(x_1*X)
TypeError: unable to coerce <type 'sage.symbolic.expression.Expression'>


How can I express unknown elements with unknown coefficients?

### How to express unknown coefficients in GF(2^8)?

I want to make computations in GF(2^8) using the Rijndael modulus X^8+X^4+X^3+X+1 and with unknown elements of GF(2^8).

For example, I need a polynomial x which is defined as x = x_7 * X^7 + x_6 * X^6 + x_5 * X^7 + ... + x_0

x.coefficients() should return [x_0, x_1, x_2, x_3, x_4, ...]

If I for example add x to y, I would expect that the result would be a term like (x_7+y_7) * X^7 + (x_6+y_6)*X^6 + ...

I tried the following:

sage: pgen = polygen(Integers(2))
sage: modulus = pgen()**8 + pgen()**4 + pgen()**3 + pgen() + 1
sage: F = FiniteField(2**8, 'X', modulus = modulus)
sage: X = F.gen()
X
sage: x_coeffs = list(var('x_%d' % i) for i in range(8))
sage: y_coeffs = list(var('y_%d' % i) for i in range(8))
sage: uF = PolynomialRing(F, 16, x_coeffs + y_coeffs); uF
Multivariate Polynomial Ring in x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, y_0, y_1, y_2, y_3, y_4, y_5, y_6, y_7 over Finite Field in a of size 2^8

sage: poly_x = uF(x_0 * X^0 + x_1 * X^1 + x_2 * X^2 + x_3 * X^3 + x_4 * X^4 + x_5 * X^5 + x_6 * X^6 + x_7 * X^7)
sage: poly_y = F(y_0 uF(y_0 * X^0 + y_1 * X^1 + y_2 * X^2 + y_3 * X^3 + y_4 * X^4 + y_5 * X^5 + y_6 * X^6 + y_7 * X^7)


(which is very much like I found it in the sources of sage.crypto.mq.rijndael_gf.RijndaelGF)

But the coefficients of poly_x and poly_y are not the variables x_0, x_1 etc. but the X^0, X^1, etc...

I also tried:

sage: F = GF(2^8, 'X')
sage: X = F.gen()
X
sage: x_coeffs = list(var('x_%d' % i) for i in range(8))
sage: y_coeffs = list(var('y_%d' % i) for i in range(8))
sage: poly_x = 0*X
sage: type(poly_x)
<type 'sage.rings.finite_rings.element_givaro.FiniteField_givaroElement'>
sage: for i in xrange(8):
....:     poly_x += x_coeffs[i] * X^i
....:
sage: poly_x
x_0 + X*x_1 + X^2*x_2 + X^3*x_3 + X^4*x_4 + X^5*x_5 + X^6*x_6 + X^7*x_7
sage: type(poly_x)
<type 'sage.symbolic.expression.Expression'>
sage: poly_x.coefficients()
[[X*x_1 + X^2*x_2 + X^3*x_3 + X^4*x_4 + X^5*x_5 + X^6*x_6 + X^7*x_7, 0],
[1, 1]]


which is also not what I want. Also, expressions like the follow lead to an error:

sage: F(x_1*X)
TypeError: unable to coerce <type 'sage.symbolic.expression.Expression'>


How can I express unknown elements with unknown coefficients?