# Addition polynomial in finite field error

This post is a wiki. Anyone with karma >750 is welcome to improve it.

I try to do some additions with finite field (GF) just like below. What happen with A?

R.<x> = GF(2)[]
K.<x> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)
A = 1 + 1
B = x + x
C = x + x^2
print A
print B
print C

Result:
2
0
x^2 + x

edit retag close merge delete

Sort by » oldest newest most voted

Note that you defined x in two different ways.

Suggestion: use different names.

To add 1 + 1 in R or in K, one needs to specify it. Otherwise 1 is the 1 in ZZ.

Here is a rewrite using different names; and addition performed in R or in K.

sage: R.<y> = GF(2)[]
....: x = polygen(ZZ)
....: K.<z> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)
....: print 'Compute 1 + 1 in R and in K'
....: print R(1) + R(1)
....: print K(1) + K(1)
....: print 'Compute y + y and z + z'
....: print y + y
....: print z + z
....: print 'Compute y + y^2 and z + z^2'
....: print y + y^2
....: print z + z^2
....:
Compute 1 + 1 in R and in K
0
0
Compute y + y and z + z
0
0
Compute y + y^2 and z + z^2
y^2 + y
z^2 + z

more

Thanks, but what happen with my code below:

R.<x> = GF(2)[]
K.<x> = GF(2^3, modulus=x^3+x+1)

M = MatrixSpace(ZZ['x'],8,8)
ab = []
for i in range(0, len(a)):
for j in range(0,len(b)):
ab.append(a[i]+b[j])
return ab

a=[0,1,x,x+2,x^2,x^2+1,x^2+x,x^2+x+1]
b=[0,1,x,x+2,x^2,x^2+1,x^2+x,x^2+x+1]
print 'Modulus used:',K.modulus()
print result


the result 1 + 1 still 2, when i dont use R.<x> = GF(2)[], my code get error... Now, my solution just not used 1. I used x^0 for replacing 1

( 2017-10-18 10:59:38 -0600 )edit

If you want to input the element 1 from the ring R, you can either use R(1) or R.one(). If you just input 1, Sage considers you mean the element 1 in ZZ.

( 2017-10-19 02:41:52 -0600 )edit

Sorry for writing this (as an) answer, but it is not fitting as a comment.

(1) Please do not give an answer as a new question. Just expand the old question or start a new one.

(2) In the original post, the minimal code that illustrates the confusion is as follows:

Let us consider the code:

sage: MyBeautifulField = GF(2)
sage: 1+1
2


Now the question can be stated: But why do we get a 2 instead of 0? I've just declared the field GF(2) to work with?!

The question has a simple answer, yes, the new field is defined, but the computing iron still lives in a general environment that still accepts all kind of inputs, including integers again.

(3) There was an immediate answer telling that it is not good (at all) to redefine implicitly that variable x. This is a common reason for mistakes. Now we have the deja vu in the question in the new answer:

R.<x> = GF(2)[]
K.<x> = GF(2^3, modulus=x^3+x+1)
M = MatrixSpace(ZZ['x'],8,8)


After the first line we can ask for the parent of x, then after the second one... get the following answers:

sage: R.<x> = GF(2)[]
sage: x.parent()
Univariate Polynomial Ring in x over Finite Field of size 2 (using NTL)
sage: K.<x> = GF(2^3, modulus=x^3+x+1)
sage: x.parent()
Finite Field in x of size 2^3
sage: x.multiplicative_order()
7


Why do you do that?! Now the problem with M is slightly more complicated. In there, to make answerers get there enthusiasm to the maximum, we are using ZZ['x']. OK, let us take this object separately...

sage: ZZ['x']
Univariate Polynomial Ring in x over Integer Ring
sage: _.gens()
(x,)


A new x appears, but somehow implicitly. No problem, since we moreover even use this implicit x in an other black box, the matrix space over the polynomial ring in the hidden variable. So we type

sage: M = MatrixSpace(ZZ['x'],8,8)
sage: x.parent()
Finite Field in x of size 2^3
sage: x.multiplicative_order()
7
sage: M.base_ring().gens()[0]
x
sage: M.base_ring().gens()[0].multiplicative_order()
---------------------------------------------------------------------------
ArithmeticError                           Traceback (most recent call last)


And in the hidden generator case we get an error trying to get the multiplicative_order of the "other x". So sage uses the same name, x, for two different objects. This is the same as people use the name Peter for the one or the other Peter in the world, from the context is / should be always clear which Peter is the addressed Peter.

(4) Now to be more confused about objects, there are canonical coercions, liftings, conversions of objects. For instance, we take the one in GF(2) and "lift it" to ZZ using the natural constructor:

sage: oneModTwo = GF(2).one()
sage: oneModTwo
1
sage: oneModTwo*2
0
sage: oneModTwo.parent()
Finite Field of size 2
sage: ZZ(oneModTwo)
1
sage: ZZ(oneModTwo).parent()
Integer Ring
sage: ZZ(oneModTwo) * 2
2


(5) Now we build a list with entries in mixed rings, for instance:

sage: add(a,b)[0]
0
Integer Ring
Integer Ring
Finite Field in x of size 2^3
x
0
Finite Field in x of size 2^3


Then apply the constructor M on the mixed list. The constructor is doing the best to convert the mixed data to the new characteristic:

sage: M.base_ring().characteristic()
0


And we get some result in characteristic zero.

(7) Of course, asking again for the modulus of K does not help. It is like a commercial during the confusion joining the result.

(8) Let us sum up with a completely new code, where Peter x has each time a different hat:

R.<X> = GF(2)[]
K.<x> = GF(2^3, modulus=X^3+X+1)
S.<y> = ZZ[]
M     = MatrixSpace( S, 8, 8 )

return [ a+b for a in aList for b in bList ]

a = [ K(0), K(1), x, x+2, x^2, x^2+1, x^2+x, x^2+x+1 ]
b = [ K(0), K(1), x, x+2, x^2, x^2+1, x^2+x, x^2+x+1 ]

result = M( add2(a, b) )
print result


And the result is an $8\times 8$ matrix with entries involving polynomials in... y, of course. (8x8 is too big to display here... but this does anyway do not matter any longer now.)

[          0           1           y           y         y^2     y^2 + 1     y^2 + y y^2 + y + 1]
[          1           0       y + 1       y + 1     y^2 + 1         y^2 y^2 + y + 1     y^2 + y]
[          y       y + 1           0           0     y^2 + y y^2 + y + 1         y^2     y^2 + 1]
[          y       y + 1           0           0     y^2 + y y^2 + y + 1         y^2     y^2 + 1]
[        y^2     y^2 + 1     y^2 + y     y^2 + y           0           1           y       y + 1]
[    y^2 + 1         y^2 y^2 + y + 1 y^2 + y + 1           1           0       y + 1           y]
[    y^2 + y y^2 + y + 1         y^2         y^2           y       y + 1           0           1]
[y^2 + y + 1     y^2 + y     y^2 + 1     y^2 + 1       y + 1           y           1           0]


Please always write clean code, and have a full control of the objects!

more

ty so much...but i need the result in x, not in y.

( 2017-10-18 22:23:36 -0600 )edit

Please state a clear question, or a task in a mathematical language.

For instance, seeing

a=[0,1,x,x+2,x^2,x^2+1,x^2+x,x^2+x+1]


without glasses, i was in the same second convinced we want to type the addition law table in K, which can easily be obtained via:

R.<X> = GF(2)[]
K.<x> = GF(2^3, modulus=X^3+X+1)
A = matrix( K, 8, 8, [ a+b for a in K for b in K ] )
A


which is...

[          0           x         x^2       x + 1     x^2 + x x^2 + x + 1     x^2 + 1           1]
[          x           0     x^2 + x           1         x^2     x^2 + 1 x^2 + x + 1       x + 1]
[        x^2     x^2 + x           0 x^2 + x + 1           x       x + 1           1     x^2 + 1]


and so on... But x+2 is there, why ...(more)

( 2017-10-22 11:43:03 -0600 )edit

Thanks...nice. Sorry for x+2 was there...my mistake.it's x+1

( 2017-10-25 00:26:03 -0600 )edit