Ask Your Question

Finding the Groebner Basis of the following Ring. Is it possible? How could I make it work with multivariate polynomials?

asked 2018-11-24 08:08:46 -0500

Lujmina gravatar image

Hey guys,

I am trying to compute the groebner basis of a polynomial system that looks like this:

e = 48;
F.<r> = GF(2)[];

for p in F.polynomials(e):
    if p.is_irreducible():

R.<x> = PolynomialRing(GF(2),name="x").quotient(p)

I = Ideal([R.random_element(),R.random_element(),R.random_element(),R.random_element(),R.random_element(),R.random_element()])
print I.groebner_basis()

However I get an error: 'Ideal_pid' object has no attribute 'groebner_basis'

I am new to Sagemath so sorry if I misunderstand something. Also, how can I possibly make R to become a multivariate system by following the same structure, using an irreducible polynomial from GF(2) as presented in this code.

Thanks guys :)

edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted

answered 2018-11-24 09:20:50 -0500

rburing gravatar image

updated 2018-11-24 10:48:23 -0500

I'm not sure what you're trying to do here. Groebner bases make sense for ideals in polynomial rings over a field. Your R is not a polynomial ring, but is itself a field, so I is either the zero ideal $(0)$ (if all random elements happen to be zero) or the unit ideal $(1) = R$. Maybe you intended to define

R.<x> = PolynomialRing(PolynomialRing(GF(2),name="a").quotient(p))

Or with more variables (when Groebner bases are more interesting):

R.<x,y,z> = PolynomialRing(PolynomialRing(GF(2),name="a").quotient(p), 3)

Since the quotient $\mathbb{F}_2[r]/(p)$ is a field $\cong \mathbb{F}_{2^e}$, it is more efficient to construct it as follows:

R.<x,y,z> = PolynomialRing(GF(2^e, name='a', modulus=p), 3)

An element y of GF(2^e) can be written as a polynomial of degree less than $e$ as follows:

K.<a> = GF(2^e, modulus=p)
R.<x> = PolynomialRing(GF(2))
y = a^48 + a^27 + 1
vy = vector(y)
sum(vy[d]*x^d for d in range(e))

By the way, this can be done with a Groebner basis of $(p) \subset \mathbb{F}_2[x]$ as well. Namely, the normal form of a polynomial w.r.t. the Groebner basis $[p]$ of $(p)$ is the one of degree less than $e$ as well:

R.ideal(p).reduce(x^48 + x^27 + 1)

In this one-variable situation, the normal form is just the remainder after polynomial division.

edit flag offensive delete link more


What I am trying to do is to convert the finite field representation into a polynomial ring with boolean coefficients. So let's take a finite field element: x^48 + x^27 +1

What I want to do is to look at this element as a polynomial ring element, so the above element will look like: Polynomial: 1*x^48 + 0*x^47 + ... + 0*x^28 + 1*x^27 + ... + 1.

Is it possible to do it in this way?

Lujmina gravatar imageLujmina ( 2018-11-24 09:26:41 -0500 )edit

Every element of the finite field $\mathbb{F}_{2^e}$ can be written (for a fixed modulus) as a polynomial of degree less than $e$ in a unique way; I added code to achieve this.

rburing gravatar imagerburing ( 2018-11-24 09:39:54 -0500 )edit

The last part was the one I was looking for, thanks man :)

Lujmina gravatar imageLujmina ( 2018-11-24 09:45:14 -0500 )edit

You're welcome :) I added a remark about how it is related to Groebner bases.

rburing gravatar imagerburing ( 2018-11-24 10:39:16 -0500 )edit

answered 2018-11-24 16:58:41 -0500

slelievre gravatar image

To complement @rburing's answer, finite field elements and polynomials over the prime field can be converted to each other easily, without the need to go through a vector.

Construct the finite field and the polynomial ring.

sage: e = 48
sage: K.<a> = GF(2^e)
sage: R.<x> = GF(2)[]

Finite field elements can be converted into polynomials.

sage: y = a^48 + a^27 + 1
sage: y
a^27 + a^25 + a^23 + a^17 + a^12 + a^11 + a^10 + a^8 + a^7 + a^3
sage: z = R(y)
sage: z
x^27 + x^25 + x^23 + x^17 + x^12 + x^11 + x^10 + x^8 + x^7 + x^3

Polynomials can be converted into finite field elements.

sage: u = x^23 + x^12 + x^4
sage: u
x^23 + x^12 + x^4
sage: v = K(u)
sage: v
a^23 + a^12 + a^4
edit flag offensive delete link more

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


Asked: 2018-11-24 08:08:46 -0500

Seen: 74 times

Last updated: Nov 24 '18