Ask Your Question
0

Polynomial modulus in QuotientRing

asked 2014-08-27 10:36:29 -0500

kekx gravatar image

updated 2015-01-14 07:37:04 -0500

FrédéricC gravatar image

I am trying to perform a polynomial modulus between elements in a QuotientRing, more or less like so:

sage: R = QuotientRing(ZZ[x], x**8+1)
sage: t = R.gen()
sage: g = 3*t^5 + 3*t^4 + 2*t^3 + 3*t^2 + t + 2
sage: a = -14*t^7 - t^6 + t^4 - 9*t^2 + 5*t + 1
sage: a.mod(g)
-14*xbar^7 - xbar^6 + xbar^4 - 9*xbar^2 + 5*xbar + 1

As you can see the modulus is not doing anything. I am not very well versed in this kind of maths, but I still believe that it should be possible to compute that modulus. Thus my question is, if it is possible to compute that modulus in sage, possibly via some kind of workaround.

I would be glad about any hints!

edit retag flag offensive close merge delete

Comments

What would you expect from such a command? In order for mod to makes sense the domain needs to have a well defined division, doesn't it?

vdelecroix gravatar imagevdelecroix ( 2014-08-28 10:29:12 -0500 )edit

1 answer

Sort by » oldest newest most voted
0

answered 2017-03-02 12:48:09 -0500

dan_fulea gravatar image

We cannot separate sage from math. So we have to do the work in both worlds.

The algebraic construction in the exercise is to first construct the ring $R=\mathbb{Z}[x]$, then to pass to the quotient $S = R/(x^8+1)$, here we consider the (class of) $3x^5 + 3x^4 + 2x^3 + 3x^2 + x + 2$, and mod out with respect to it too.

Then it is a good idea to mod out directly with respect to the two polynomials. In sage:

R.<x> = PolynomialRing( ZZ )
f = x^8 +1
g = 3*x^5 + 3*x^4 + 2*x^3 + 3*x^2 + x + 2
J = R.ideal( f, g )
S = R.quotient( J )

This is a finite ring, but the corresponding methods are not implemented. So we have to do the work on the theoretical side first. It is known, that the ideal $J$ is related to the resultant of $f$ and $g$. Since it is a short game to pop it up by using the euclidian algorithm in $R$, we will do play it. But in order to do this, we pass to rationals. (Else sage will not do much with f % g , and we need the rest.)

RQ.<x> = PolynomialRing( QQ )
f = x^8 +1
g = 3*x^5 + 3*x^4 + 2*x^3 + 3*x^2 + x + 2
J = RQ.ideal( f, g )
SQ = RQ.quotient( J )

print "SQ is", SQ
print "J is (over QQ) the ideal", J

r = f; s = g
while r.degree() > 0:
    r, s = s, r % s
    print "r = %s and s = %s" % ( r, s )

And we get:

SQ is Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus 1
J is (over QQ) the ideal Principal ideal (1) of Univariate Polynomial Ring in x over Rational

And for the euclidean algorithm:

r = 3*x^5 + 3*x^4 + 2*x^3 + 3*x^2 + x + 2 and s = 10/9*x^4 - 2/9*x^3 + 11/9*x^2 + 13/9
r = 10/9*x^4 - 2/9*x^3 + 11/9*x^2 + 13/9 and s = -29/50*x^3 - 24/25*x^2 - 29/10*x - 67/25
r = -29/50*x^3 - 24/25*x^2 - 29/10*x - 67/25 and s = -775/841*x^2 + 150/29*x + 9225/841
r = -775/841*x^2 + 150/29*x + 9225/841 and s = -803996/24025*x - 253982/4805
r = -803996/24025*x - 253982/4805 and s = 96124025/192155044
r = 96124025/192155044 and s = 0

We had to introduce denominators, but it is clear how to multiply with them in each line, in order to get an operation over integers. It may happen, that some denominators "loose or win factors on the road", but the message is clear - say - up to inverting 192155044. The intermediate result in the line with r = -803996/24025x - 253982/4805 tells us, that $x$ may be replaced by the solution of the equation r=0 (for this r). We store the result x == (-755/478) obtained from: var( 'x' ); solve( -803996/24025x - 253982/4805 == 0, x )

The elegant way of doing the computations is by requiring directly:

sage: q, u, v = f.xgcd( g )    # gcd with u, v such that uf + gv is the gcd.

sage: u, v
(-717/4001*x^4 + 831/8002*x^3 - 3047/8002*x^2 - 1769/8002*x + 4276/4001,
 239/4001*x^7 - 755/8002*x^6 + 726/4001*x^5 - 837/8002*x^4 - 1193/4001*x^3 + 1425/8002*x^2 + 511/4001*x - 275/8002)

sage: U, V = u * 8002, v * 8002
sage: U, V
(-1434*x^4 + 831*x^3 - 3047*x^2 - 1769*x + 8552,
 478*x^7 - 755*x^6 + 1452*x^5 - 837*x^4 - 2386*x^3 + 1425*x^2 + 1022*x - 275)

sage: U * f + V * g
8002

We may be also interested to see:

sage: f.resultant( g ).factor()
2^2 * 4001

So which number should we trust? 2 * 4001 or rather 2^2 * 4001 ? Which are the invariant factors of the quotient, seen as a torsion module over integers. (Ignoring the ring structure first.) We will show in a second that $S$ is isomorphic as a module to $(\mathbb{Z}/2)^2\times (\mathbb{Z}/4001)$.

The map to the first copy factors as $S=\mathbb{Z}[x]/(f,g)\to (\mathbb{Z}/2)[x]/(f,g) \cong \mathbb{F}_2[x]/(x+1)^2$. To see this, we ask sage for...

R2.<x> = PolynomialRing( GF(2) )
f = x^8 +1
g = 3*x^5 + 3*x^4 + 2*x^3 + 3*x^2 + x + 2
print "f modulo 2 is %s ." % factor( f )
print "g modulo 2 is %s ." % factor( g )
print "GF(2)[ x ] is a UFD, so the gcd is seen to be: %s" % f.gcd(g).factor()

And we get:

f modulo 2 is (x + 1)^8 .
g modulo 2 is x * (x + 1)^2 * (x^2 + x + 1) .
GF(2)[ x ] is a UFD, so the gcd is seen to be: (x + 1)^2

And in a parallel manner:

R4001.<x> = PolynomialRing( GF(4001) )
f = x^8 +1
g = 3*x^5 + 3*x^4 + 2*x^3 + 3*x^2 + x + 2
print "f modulo 4001 is %s ." % factor( f )
print "g modulo 4001 is %s ." % factor( g )
print "GF(4001)[ x ] is a UFD, so the gcd is seen to be: %s" % f.gcd(g).factor()

And we get:

f modulo 4001 is (x + 1115) * (x + 1413) * (x + 1866) * (x + 1970) * (x + 2031) * (x + 2135) * (x + 2588) * (x + 2886) .
g modulo 4001 is (3) * (x + 2588) * (x^4 + 1414*x^3 + 150*x^2 + 3899*x + 1244) .
GF(4001)[ x ] is a UFD, so the gcd is seen to be: x + 2588

So we can write down a (ring) map from $S$ to $\mathbb{F_2}[x]/(x+1)^2\times \mathbb{F}_{4001}[x]/(x+2588)= \mathbb{F_2}[x]/(x+1)^2\times \mathbb{F}_{4001}$, induced by sending $x$ to (the class of) the element $(\qquad x\mod (x+1)^2\mathbb{F}_2[x]\qquad ,\qquad -2588\qquad )$.

And we can further sent this element to $\mathbb{Z}/2\times \mathbb{Z}/4001\cong \mathbb{Z}/8002$, the composition being $x\to(-1,-2588) \cong 1413$. Note also the "coincidence":

sage: Mod( (-755/478), 4001 )
1413
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

Stats

Asked: 2014-08-27 10:36:29 -0500

Seen: 135 times

Last updated: Mar 02