Ask Your Question
1

Get coefficients of a polynomial in quotient ring

asked 2014-11-18 13:04:35 +0100

NumberFour gravatar image

updated 2020-06-01 11:34:36 +0100

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

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
1

answered 2014-11-18 14:28:22 +0100

slelievre gravatar image

updated 2014-11-18 15:20:32 +0100

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

Comments

Thanks alot! This helped

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

Pas mal du tout !

tmonteil gravatar imagetmonteil ( 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)
tmonteil gravatar imagetmonteil ( 2014-11-18 23:57:12 +0100 )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: 2014-11-18 13:04:35 +0100

Seen: 2,153 times

Last updated: Nov 18 '14