Revision history [back]
 | 1 | initial version |
Inverting polynomial $p$ modulo $I$ can be done by introducing an additional "heaviest" variable $t$ and computing Groebner basis $B$ of $I\cup {tp-1}$. It $p$ is invertible, then $B$ will contain a polynomial of the form $t-p^{-1}$. Here is a sample code:
def invert_poly(p,I):
t = I.ring().gens()[0]
q = ideal(I.gens()+[t*p - 1]).groebner_basis()[0]
if q.monomial_coefficient(t)==1:
return -q.specialization({t:0})
return None
R.<t,x,y,z> = PolynomialRing(GF(2),order='lex')
I = R.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
For example, invert_poly(x+y^2,I) returns x^3*y^2 + x*y.
| | 2 | No.2 Revision |
Inverting polynomial $p$ modulo $I$ can be done by introducing an additional "heaviest" variable $t$ and computing Groebner basis $B$ of $I\cup {tp-1}$. \{tp-1\}$. It $p$ is invertible, then $B$ will contain a polynomial of the form $t-p^{-1}$. Here is a sample code:
def invert_poly(p,I):
t = I.ring().gens()[0]
q = ideal(I.gens()+[t*p - 1]).groebner_basis()[0]
if q.monomial_coefficient(t)==1:
return -q.specialization({t:0})
return None
R.<t,x,y,z> = PolynomialRing(GF(2),order='lex')
I = R.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
For example, invert_poly(x+y^2,I) returns x^3*y^2 + x*y.
| | 3 | No.3 Revision |
Inverting polynomial $p$ modulo $I$ can be done by introducing an additional "heaviest" variable $t$ and computing Groebner basis $B$ of $I\cup \{tp-1\}$. It $p$ is invertible, then $B$ will contain a polynomial of the form $t-p^{-1}$. Here is a sample code:
Ring.<x,y,z>
=For example, invert_poly(x+y^2,I) returns x^3*y^2 + x*y.
| | 4 | No.4 Revision |
Inverting polynomial $p$ modulo $I$ can be done by introducing an additional "heaviest" variable $t$ and computing Groebner basis $B$ of $I\cup \{tp-1\}$. It $p$ is invertible, then $B$ will contain a polynomial of the form $t-p^{-1}$. Here is a sample code:
def invert_poly(p,J): R = PolynomialRing( J.base_ring(), ['t']+[str(v) for v in J.ring().gens()], order='lex') t = R.gens()[0] q = ideal( [R(g) for g in J.gens()] + [t*p - 1] ).groebner_basis()[0] if q.monomial_coefficient(t)==1: return q.specialization({t:0}) return None
Ring.<x,y,z> = PolynomialRing(GF(2)) I = Ring.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
For example, invert_poly(x+y^2,I) returns x^3*y^2 + x*y.
| | 5 | No.5 Revision |
Inverting polynomial $p$ modulo $I$ can be done by introducing an additional "heaviest" variable $t$ and computing Groebner basis $B$ of $I\cup \{tp-1\}$. It $p$ is invertible, then $B$ will contain a polynomial of the form $t-p^{-1}$. Here is a sample code:
For example, invert_poly(x+y^2,I) returns x^3*y^2 + x*y.
| | 6 | No.6 Revision |
Inverting polynomial $p$ modulo $I$ ideal $J$ can be done by introducing an additional "heaviest" variable $t$ and computing Groebner basis $B$ of $I\cup \{tp-1\}$. It $p$ is invertible, then $B$ will contain a polynomial of the form $t-p^{-1}$. Here is a sample code:
def invert_poly(p,J):
R = PolynomialRing( J.base_ring(), ['t']+[str(v) for v in J.ring().gens()], order='lex')
t = R.gens()[0]
q = ideal( [R(g) for g in J.gens()] + [t*p - 1] ).groebner_basis()[0]
if q.monomial_coefficient(t)==1:
return q.specialization({t:0})
return None
For example,
For example, returns invert_poly(x+y^2,I) x^3*y^2 + x*y.
| | 7 | No.7 Revision |
Inverting polynomial $p$ modulo ideal $J$ can be done by introducing an additional "heaviest" variable $t$ and computing Groebner basis $B$ of $I\cup \{tp-1\}$. It $p$ is invertible, then $B$ will contain a polynomial of the form $t-p^{-1}$. Here is a sample code:
def invert_poly(p,J):
R = PolynomialRing( J.base_ring(), ['t']+[str(v) for v in J.ring().gens()], order='lex')
t = R.gens()[0]
q = ideal( [R(g) for g in J.gens()] + [t*p - 1] ).groebner_basis()[0]
if q.monomial_coefficient(t)==1:
return q.specialization({t:0})
-q.specialization({t:0})
return None
For example,
Ring.<x,y,z> = PolynomialRing(GF(2))
I = Ring.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
invert_poly(x+y^2,I)
returns x^3*y^2 + x*y.
| | 8 | No.8 Revision |
Inverting polynomial $p$ modulo ideal $J$ can be done by introducing an additional "heaviest" variable $t$ and computing Groebner basis $B$ of $I\cup \{tp-1\}$. It $p$ is invertible, then $B$ will contain a polynomial of the form $t-p^{-1}$. Here is a sample code:
def invert_poly(p,J):
R = PolynomialRing( J.base_ring(), ['t']+[str(v) ['newvar']+[str(v) for v in J.ring().gens()], order='lex')
t = R.gens()[0]
q = ideal( [R(g) for g in J.gens()] + [t*p - 1] ).groebner_basis()[0]
if q.monomial_coefficient(t)==1:
return -q.specialization({t:0})
return None
For example,
Ring.<x,y,z> = PolynomialRing(GF(2))
I = Ring.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
invert_poly(x+y^2,I)
returns x^3*y^2 + x*y.
| | 9 | No.9 Revision |
Inverting polynomial $p$ modulo ideal $J$ can be done by introducing an additional "heaviest" variable $t$ and computing Groebner basis $B$ of $I\cup $J\cup \{tp-1\}$. It $p$ is invertible, then $B$ will contain a polynomial of the form $t-p^{-1}$. Here is a sample code:
def invert_poly(p,J):
R = PolynomialRing( J.base_ring(), ['newvar']+[str(v) for v in J.ring().gens()], order='lex')
t = R.gens()[0]
q = ideal( [R(g) for g in J.gens()] + [t*p - 1] ).groebner_basis()[0]
if q.monomial_coefficient(t)==1:
return -q.specialization({t:0})
return None
For example,
Ring.<x,y,z> = PolynomialRing(GF(2))
I = Ring.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
invert_poly(x+y^2,I)
returns x^3*y^2 + x*y.
| | 10 | No.10 Revision |
Inverting polynomial $p$ modulo ideal $J$ can be done by introducing an additional "heaviest" variable $t$ and computing Groebner basis $B$ of $J\cup \{tp-1\}$. It $p$ is invertible, then $B$ will contain a polynomial of the form $t-p^{-1}$. Here is a sample code:
def invert_poly(p,J):
R = PolynomialRing( J.base_ring(), ['newvar']+[str(v) for v in J.ring().gens()], order='lex')
t = R.gens()[0]
q r = ideal( [R(g) for g in J.gens()] + [t*p - 1] ).groebner_basis()[0]
if q.monomial_coefficient(t)==1:
r.monomial_coefficient(t)==1:
q = -r.specialization({t:0})
if J.reduce(p*q)==1:
return -q.specialization({t:0})
q
return None
For example,example, to invert 1+x+y we run
Ring.<x,y,z> = PolynomialRing(GF(2))
I = Ring.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
invert_poly(x+y^2,I)
invert_poly(1+x+y,I)
returns which gives x^4*y^3 + x^3*y^4 + x^4*y^2 + x^2*y^4 + x^3*y^2 + x*yx^2*y^3 + x^4 + x^3*y + x*y^3 + y^4 + x^3 + y^3 + x + y + 1.
| | 11 | No.11 Revision |
Inverting polynomial $p$ modulo ideal $J$ can be done by introducing an additional "heaviest" variable $t$ and computing Groebner basis $B$ of $J\cup \{tp-1\}$. It If $p$ is invertible, then $B$ will contain a polynomial of the form $t-p^{-1}$. Here is a sample code:
def invert_poly(p,J):
R = PolynomialRing( J.base_ring(), ['newvar']+[str(v) for v in J.ring().gens()], order='lex')
t = R.gens()[0]
r = ideal( [R(g) for g in J.gens()] + [t*p - 1] ).groebner_basis()[0]
if r.monomial_coefficient(t)==1:
q = -r.specialization({t:0})
if J.reduce(p*q)==1:
return q
return None
For example, to invert 1+x+y we run
Ring.<x,y,z> = PolynomialRing(GF(2))
I = Ring.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
invert_poly(1+x+y,I)
which gives x^4*y^3 + x^3*y^4 + x^4*y^2 + x^2*y^4 + x^3*y^2 + x^2*y^3 + x^4 + x^3*y + x*y^3 + y^4 + x^3 + y^3 + x + y + 1.
| | 12 | No.12 Revision |
Inverting polynomial $p$ modulo ideal $J$ can be done by introducing an additional "heaviest" variable $t$ and computing Groebner basis $B$ of $J\cup \{tp-1\}$. If $p$ is invertible, then $B$ will contain a polynomial of the form $t-p^{-1}$. Here is a sample code:
def invert_poly(p,J):
R = PolynomialRing( J.base_ring(), ['newvar']+[str(v) for v in J.ring().gens()], order='lex')
t = R.gens()[0]
r = ideal( [R(g) for g in J.gens()] + [t*p - 1] ).groebner_basis()[0]
if r.monomial_coefficient(t)==1:
q = -r.specialization({t:0})
if J.reduce(p*q)==1:
return q
return None
For example, to invert 1+x+y we run
Ring.<x,y,z> = PolynomialRing(GF(2))
I = Ring.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
invert_poly(1+x+y,I)
which gives x^4*y^3 + x^3*y^4 + x^4*y^2 + x^2*y^4 + x^3*y^2 + x^2*y^3 + x^4 + x^3*y + x*y^3 + y^4 + x^3 + y^3 + x + y + 1.
| | 13 | No.13 Revision |
Inverting polynomial $p$ modulo ideal $J$ can be done by introducing an additional "heaviest" variable $t$ and computing Groebner basis $B$ of $J\cup \{tp-1\}$. If $p$ is invertible, then $B$ will contain a polynomial of the form $t-p^{-1}$. Here is a sample code:
def invert_poly(p,J):
R = PolynomialRing( J.base_ring(), ['newvar']+[str(v) ['var_t']+[str(v) for v in J.ring().gens()], order='lex')
t = R.gens()[0]
r = ideal( [R(g) for g in J.gens()] + [t*p - 1] ).groebner_basis()[0]
q = -r.specialization({t:0})
if J.reduce(p*q)==1:
return q
return None
For example, to invert 1+x+y we run
Ring.<x,y,z> = PolynomialRing(GF(2))
I = Ring.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
invert_poly(1+x+y,I)
which gives x^4*y^3 + x^3*y^4 + x^4*y^2 + x^2*y^4 + x^3*y^2 + x^2*y^3 + x^4 + x^3*y + x*y^3 + y^4 + x^3 + y^3 + x + y + 1.
| | 14 | No.14 Revision |
Inverting polynomial $p$ modulo ideal $J$ can be done by introducing an additional "heaviest" variable $t$ and computing Groebner basis $B$ of $J\cup \{tp-1\}$. If $p$ is invertible, then the heaviest polynomial in $B$ will contain a polynomial of have the form $t-p^{-1}$. Here is a sample code:
def invert_poly(p,J):
R = PolynomialRing( J.base_ring(), ['var_t']+[str(v) for v in J.ring().gens()], order='lex')
t = R.gens()[0]
r = ideal( [R(g) for g in J.gens()] + [t*p - 1] ).groebner_basis()[0]
q = -r.specialization({t:0})
if J.reduce(p*q)==1:
return q
return None
For example, to invert 1+x+y we run
Ring.<x,y,z> = PolynomialRing(GF(2))
I = Ring.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
invert_poly(1+x+y,I)
which gives x^4*y^3 + x^3*y^4 + x^4*y^2 + x^2*y^4 + x^3*y^2 + x^2*y^3 + x^4 + x^3*y + x*y^3 + y^4 + x^3 + y^3 + x + y + 1.
| | 15 | No.15 Revision |
Inverting a polynomial $p$ modulo an ideal $J$ can be done by introducing an additional "heaviest" variable $t$ and computing Groebner basis $B$ of $J\cup \{tp-1\}$. If $p$ is invertible, then using .inverse_mod() method - like in the heaviest polynomial in $B$ will have the form $t-p^{-1}$. Here is a sample code:example below:
def invert_poly(p,J):
R = PolynomialRing( J.base_ring(), ['var_t']+[str(v) for v in J.ring().gens()], order='lex')
t = R.gens()[0]
r = ideal( [R(g) for g in J.gens()] + [t*p - 1] ).groebner_basis()[0]
q = -r.specialization({t:0})
if J.reduce(p*q)==1:
return q
return None
For example, to invert 1+x+y we run
Ring.<x,y,z> R.<x,y,z> = PolynomialRing(GF(2))
I = Ring.ideal( R.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
invert_poly(1+x+y,I)
(1+x+y).inverse_mod(I)
which gives That is, inversion of 1+x+y modulo I equals x^4*y^3 + x^3*y^4 + x^4*y^2 + x^2*y^4 + x^3*y^2 + x^2*y^3 + x^4 + x^3*y + x*y^3 + y^4 + x^3 + y^3 + x + y + 1.
| | 16 | No.16 Revision |
Inverting a polynomial modulo an ideal can be done by using .inverse_mod() method - like in the example below:
R.<x,y,z> = PolynomialRing(GF(2))
I = R.ideal( [x^5 + 1, y^5 + 1, z^64 + 1] )
(1+x+y).inverse_mod(I)
That is, which gives inversion of 1+x+y modulo I equals as x^4*y^3 + x^3*y^4 + x^4*y^2 + x^2*y^4 + x^3*y^2 + x^2*y^3 + x^4 + x^3*y + x*y^3 + y^4 + x^3 + y^3 + x + y + 1.
