Ask Your Question
0

Addition polynomial in finite field error

asked 2017-10-17 09:46:19 -0600

this post is marked as community wiki

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 flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
0

answered 2017-10-17 11:11:43 -0600

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
edit flag offensive delete link more

Comments

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)
def add(a, b):
    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]
result=M(add(a, b))
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

Niyamabrata gravatar imageNiyamabrata ( 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.

slelievre gravatar imageslelievre ( 2017-10-19 02:41:52 -0600 )edit
0

answered 2017-10-18 13:13:14 -0600

dan_fulea gravatar image

updated 2017-10-18 13:17:08 -0600

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
sage: add(a,b)[0].parent()
Integer Ring
sage: add(a,b)[1].parent()
Integer Ring
sage: add(a,b)[2].parent()
Finite Field in x of size 2^3
sage: add(a,b)[2]
x
sage: add(a,b)[63]
0
sage: add(a,b)[63].parent()
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 )

def add2(aList, bList):
    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!

edit flag offensive delete link more

Comments

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

Niyamabrata gravatar imageNiyamabrata ( 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)

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

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

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

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-10-17 09:46:19 -0600

Seen: 52 times

Last updated: Oct 18