ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 24 Nov 2018 16:58:41 -0600Finding the Groebner Basis of the following Ring. Is it possible? How could I make it work with multivariate polynomials?https://ask.sagemath.org/question/44409/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 :)Sat, 24 Nov 2018 08:08:46 -0600https://ask.sagemath.org/question/44409/finding-the-groebner-basis-of-the-following-ring-is-it-possible-how-could-i-make-it-work-with-multivariate-polynomials/Answer by slelievre for <p>Hey guys,</p>
<p>I am trying to compute the groebner basis of a polynomial system that looks like this:</p>
<pre><code>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()
</code></pre>
<p>However I get an error: 'Ideal_pid' object has no attribute 'groebner_basis'</p>
<p>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.</p>
<p>Thanks guys :)</p>
https://ask.sagemath.org/question/44409/finding-the-groebner-basis-of-the-following-ring-is-it-possible-how-could-i-make-it-work-with-multivariate-polynomials/?answer=44423#post-id-44423To 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
Sat, 24 Nov 2018 16:58:41 -0600https://ask.sagemath.org/question/44409/finding-the-groebner-basis-of-the-following-ring-is-it-possible-how-could-i-make-it-work-with-multivariate-polynomials/?answer=44423#post-id-44423Answer by rburing for <p>Hey guys,</p>
<p>I am trying to compute the groebner basis of a polynomial system that looks like this:</p>
<pre><code>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()
</code></pre>
<p>However I get an error: 'Ideal_pid' object has no attribute 'groebner_basis'</p>
<p>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.</p>
<p>Thanks guys :)</p>
https://ask.sagemath.org/question/44409/finding-the-groebner-basis-of-the-following-ring-is-it-possible-how-could-i-make-it-work-with-multivariate-polynomials/?answer=44415#post-id-44415I'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.Sat, 24 Nov 2018 09:20:50 -0600https://ask.sagemath.org/question/44409/finding-the-groebner-basis-of-the-following-ring-is-it-possible-how-could-i-make-it-work-with-multivariate-polynomials/?answer=44415#post-id-44415Comment by rburing for <p>I'm not sure what you're trying to do here. Groebner bases make sense for ideals in polynomial rings over a field. Your <code>R</code> is not a polynomial ring, but is itself a field, so <code>I</code> 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</p>
<pre><code>R.<x> = PolynomialRing(PolynomialRing(GF(2),name="a").quotient(p))
</code></pre>
<p>Or with more variables (when Groebner bases are more interesting): </p>
<pre><code>R.<x,y,z> = PolynomialRing(PolynomialRing(GF(2),name="a").quotient(p), 3)
</code></pre>
<p>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:</p>
<pre><code>R.<x,y,z> = PolynomialRing(GF(2^e, name='a', modulus=p), 3)
</code></pre>
<hr>
<p>An element <code>y</code> of <code>GF(2^e)</code> can be written as a polynomial of degree less than $e$ as follows:</p>
<pre><code>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))
</code></pre>
<p>By the way, this can be done with a Groebner basis of $(p) \subset \mathbb{F}_2[x]$ as well. Namely, the <em>normal form</em> of a polynomial w.r.t. the Groebner basis $[p]$ of $(p)$ is the one of degree less than $e$ as well:</p>
<pre><code>R.ideal(p).reduce(x^48 + x^27 + 1)
</code></pre>
<p>In this one-variable situation, the normal form is just the remainder after polynomial division.</p>
https://ask.sagemath.org/question/44409/finding-the-groebner-basis-of-the-following-ring-is-it-possible-how-could-i-make-it-work-with-multivariate-polynomials/?comment=44420#post-id-44420You're welcome :) I added a remark about how it is related to Groebner bases.Sat, 24 Nov 2018 10:39:16 -0600https://ask.sagemath.org/question/44409/finding-the-groebner-basis-of-the-following-ring-is-it-possible-how-could-i-make-it-work-with-multivariate-polynomials/?comment=44420#post-id-44420Comment by Lujmina for <p>I'm not sure what you're trying to do here. Groebner bases make sense for ideals in polynomial rings over a field. Your <code>R</code> is not a polynomial ring, but is itself a field, so <code>I</code> 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</p>
<pre><code>R.<x> = PolynomialRing(PolynomialRing(GF(2),name="a").quotient(p))
</code></pre>
<p>Or with more variables (when Groebner bases are more interesting): </p>
<pre><code>R.<x,y,z> = PolynomialRing(PolynomialRing(GF(2),name="a").quotient(p), 3)
</code></pre>
<p>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:</p>
<pre><code>R.<x,y,z> = PolynomialRing(GF(2^e, name='a', modulus=p), 3)
</code></pre>
<hr>
<p>An element <code>y</code> of <code>GF(2^e)</code> can be written as a polynomial of degree less than $e$ as follows:</p>
<pre><code>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))
</code></pre>
<p>By the way, this can be done with a Groebner basis of $(p) \subset \mathbb{F}_2[x]$ as well. Namely, the <em>normal form</em> of a polynomial w.r.t. the Groebner basis $[p]$ of $(p)$ is the one of degree less than $e$ as well:</p>
<pre><code>R.ideal(p).reduce(x^48 + x^27 + 1)
</code></pre>
<p>In this one-variable situation, the normal form is just the remainder after polynomial division.</p>
https://ask.sagemath.org/question/44409/finding-the-groebner-basis-of-the-following-ring-is-it-possible-how-could-i-make-it-work-with-multivariate-polynomials/?comment=44419#post-id-44419The last part was the one I was looking for, thanks man :)Sat, 24 Nov 2018 09:45:14 -0600https://ask.sagemath.org/question/44409/finding-the-groebner-basis-of-the-following-ring-is-it-possible-how-could-i-make-it-work-with-multivariate-polynomials/?comment=44419#post-id-44419Comment by rburing for <p>I'm not sure what you're trying to do here. Groebner bases make sense for ideals in polynomial rings over a field. Your <code>R</code> is not a polynomial ring, but is itself a field, so <code>I</code> 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</p>
<pre><code>R.<x> = PolynomialRing(PolynomialRing(GF(2),name="a").quotient(p))
</code></pre>
<p>Or with more variables (when Groebner bases are more interesting): </p>
<pre><code>R.<x,y,z> = PolynomialRing(PolynomialRing(GF(2),name="a").quotient(p), 3)
</code></pre>
<p>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:</p>
<pre><code>R.<x,y,z> = PolynomialRing(GF(2^e, name='a', modulus=p), 3)
</code></pre>
<hr>
<p>An element <code>y</code> of <code>GF(2^e)</code> can be written as a polynomial of degree less than $e$ as follows:</p>
<pre><code>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))
</code></pre>
<p>By the way, this can be done with a Groebner basis of $(p) \subset \mathbb{F}_2[x]$ as well. Namely, the <em>normal form</em> of a polynomial w.r.t. the Groebner basis $[p]$ of $(p)$ is the one of degree less than $e$ as well:</p>
<pre><code>R.ideal(p).reduce(x^48 + x^27 + 1)
</code></pre>
<p>In this one-variable situation, the normal form is just the remainder after polynomial division.</p>
https://ask.sagemath.org/question/44409/finding-the-groebner-basis-of-the-following-ring-is-it-possible-how-could-i-make-it-work-with-multivariate-polynomials/?comment=44418#post-id-44418Every 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.Sat, 24 Nov 2018 09:39:54 -0600https://ask.sagemath.org/question/44409/finding-the-groebner-basis-of-the-following-ring-is-it-possible-how-could-i-make-it-work-with-multivariate-polynomials/?comment=44418#post-id-44418Comment by Lujmina for <p>I'm not sure what you're trying to do here. Groebner bases make sense for ideals in polynomial rings over a field. Your <code>R</code> is not a polynomial ring, but is itself a field, so <code>I</code> 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</p>
<pre><code>R.<x> = PolynomialRing(PolynomialRing(GF(2),name="a").quotient(p))
</code></pre>
<p>Or with more variables (when Groebner bases are more interesting): </p>
<pre><code>R.<x,y,z> = PolynomialRing(PolynomialRing(GF(2),name="a").quotient(p), 3)
</code></pre>
<p>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:</p>
<pre><code>R.<x,y,z> = PolynomialRing(GF(2^e, name='a', modulus=p), 3)
</code></pre>
<hr>
<p>An element <code>y</code> of <code>GF(2^e)</code> can be written as a polynomial of degree less than $e$ as follows:</p>
<pre><code>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))
</code></pre>
<p>By the way, this can be done with a Groebner basis of $(p) \subset \mathbb{F}_2[x]$ as well. Namely, the <em>normal form</em> of a polynomial w.r.t. the Groebner basis $[p]$ of $(p)$ is the one of degree less than $e$ as well:</p>
<pre><code>R.ideal(p).reduce(x^48 + x^27 + 1)
</code></pre>
<p>In this one-variable situation, the normal form is just the remainder after polynomial division.</p>
https://ask.sagemath.org/question/44409/finding-the-groebner-basis-of-the-following-ring-is-it-possible-how-could-i-make-it-work-with-multivariate-polynomials/?comment=44416#post-id-44416What 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?Sat, 24 Nov 2018 09:26:41 -0600https://ask.sagemath.org/question/44409/finding-the-groebner-basis-of-the-following-ring-is-it-possible-how-could-i-make-it-work-with-multivariate-polynomials/?comment=44416#post-id-44416