Ask Your Question
1

Get coefficients of a polynomial in quotient ring

asked 10 years ago

NumberFour gravatar image

updated 4 years ago

FrédéricC gravatar image

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

Preview: (hide)

1 Answer

Sort by » oldest newest most voted
1

answered 10 years ago

slelievre gravatar image

updated 10 years ago

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

In summary, a contracted answer to your question is:

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
Preview: (hide)
link

Comments

Thanks alot! This helped

NumberFour gravatar imageNumberFour ( 10 years ago )

Pas mal du tout !

tmonteil gravatar imagetmonteil ( 10 years ago )

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)
tmonteil gravatar imagetmonteil ( 10 years ago )

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: 10 years ago

Seen: 2,266 times

Last updated: Nov 18 '14