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

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():
break;

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

Sort by ยป oldest newest most voted

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.

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?

( 2018-11-24 09:26:41 -0600 )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.

( 2018-11-24 09:39:54 -0600 )edit
1

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

( 2018-11-24 09:45:14 -0600 )edit

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

( 2018-11-24 10:39:16 -0600 )edit

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

more