# Get coefficients of a polynomial in quotient ring

Let say I have the following quotient ring:

F.<t> = PolynomialRing(GF(2), 'x').quotient(x^128 + x^7 + x^2 + x + 1);


Then I create a polynomial, for example t^128 which yields:

t^7 + t^2 + t + 1


Now how do I obtain the array of coefficients of this polynomial? Or, similarly, how do I actually substitute 2 for t and evaluate this polynomial? The subs method doesn't work. (Probably the polynomial needs to be coerced to other ring with base field where 2 != 0).

edit retag close merge delete

Sort by » oldest newest most voted

### Exploring

Here is one way we could explore the possibilities in Sage based on your question.

First, it is always a good idea to give names to the objects you are manipulating:

sage: R.<x> = PolynomialRing(GF(2))
sage: F.<t> = R.quotient(x^128 + x^7 + x^2 + x + 1)
sage: a = t^7 + t^2 + t + 1


Then you can investigate the methods you can apply to them. Type

sage: a.


then the TAB key. Among the methods is a method called list.

sage: l = a.list()
sage: len(l)
128
sage: l[:20]
[1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]


Now you can get a polynomial from a list of coefficients:

sage: p = R(l)
sage: p
x^7 + x^2 + x + 1


You can evaluate this polynomial at 2

sage: p(2)
1


or substitute:

sage: p.subs(x=2)
1


We get 1 because in R, computations are modulo 2.

One way to get around that is to define the polynomial ring over ZZ:

sage: S = PolynomialRing(ZZ,'x')


and create a polynomial in this ring from the list l:

sage: q = S(l)
x^7 + x^2 + x + 1


and we can then evaluate

sage: q(2)
135


or substitute

sage: q.subs(x=2)
135


Another way is to directly change ring by letting

sage: q = p.change_ring(ZZ); q
x^7 + x^2 + x + 1
sage: q(2)
135


sage: a = t^7 + t^2 + t + 1
sage: R(a.list()).change_ring(ZZ)(2)
135


### Working with finite fields

It seems you want to work with the finite field with 2^128 elements.

The easiest way to do that is

sage: K.<t> = GF(2^128); K
Finite Field in t of size 2^128


As it turns out, the minimal polynomial for the generator t in K is exactly the polynomial you used in your quotient ring.

sage: p = t.minpoly(); p
x^128 + x^7 + x^2 + x + 1


Indeed:

sage: a = t^128; a
t^7 + t^2 + t + 1


Now it is easier to transform a into a polynomial:

sage: q = a.polynomial(); q
t^7 + t^2 + t + 1


We can evaluate this polynomial at 2:

sage: q(2)
1


This is again because q is defined over GF(2). Change ring:

sage: r = q.change_ring(ZZ); r
t^7 + t^2 + t + 1
sage: r(2)
135

more

Thanks alot! This helped

( 2014-11-18 18:06:37 +0100 )edit

Pas mal du tout !

( 2014-11-18 23:53:30 +0100 )edit

A micro remark on @slelievre answer, you can see the difference between a and q as follows:

sage: a.parent()
Finite Field in t of size 2^128

sage: q.parent()
Univariate Polynomial Ring in t over Finite Field of size 2 (using NTL)

( 2014-11-18 23:57:12 +0100 )edit