ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 20 Jul 2012 18:08:10 -0500Polynomial arithmetic modulo prime powershttp://ask.sagemath.org/question/9166/polynomial-arithmetic-modulo-prime-powers/I'm trying to do some operations with polynomials over $Z/p^nZ$ and I'm stuck on some basic things:
1) Is it possible in SAGE to long divide two polynomials in $Z/p^nZ[x]$?
2) Is it possible in SAGE to factor a polynomial in $Z/p^nZ[x]$?
Am I missing something about the basic functionality of (1)? Is this really something that I need to program myself??
Fri, 20 Jul 2012 07:37:12 -0500http://ask.sagemath.org/question/9166/polynomial-arithmetic-modulo-prime-powers/Answer by calc314 for <p>I'm trying to do some operations with polynomials over $Z/p^nZ$ and I'm stuck on some basic things:</p>
<p>1) Is it possible in SAGE to long divide two polynomials in $Z/p^nZ[x]$?</p>
<p>2) Is it possible in SAGE to factor a polynomial in $Z/p^nZ[x]$?</p>
<p>Am I missing something about the basic functionality of (1)? Is this really something that I need to program myself??</p>
http://ask.sagemath.org/question/9166/polynomial-arithmetic-modulo-prime-powers/?answer=13837#post-id-13837Here is what I've found. You can define the coefficients in the ring `R=Integer(9)`. Then, define the polynomial ring `K.<x>=R[]`. After that, you can do calculations in the polynomial ring and can find the quotient and remainder. That handles the long division. See below.
sage: R=Integers(9)
sage: list(R)
[0, 1, 2, 3, 4, 5, 6, 7, 8]
sage: K.<x>=R[]
sage: p1=x^4-3*x
sage: print p1
x^4 + 6*x
sage: p2=x^2+5
sage: p1*p2
x^6 + 5*x^4 + 6*x^3 + 3*x
sage: p1.quo_rem(p2)
(x^2 + 4, 6*x + 7)
sage: (x^2+4)*p2+(6*x+7)
x^4 + 6*x
In terms of factoring, I get an error, since $Z/p^nZ[x]$ is not an unique factorization domain, $n>1$.
sage: p1.factor()
Traceback (most recent call last):
...
NotImplementedError: factorization of polynomials over rings with composite characteristic is not implemented
So this won't work for $p^n$ with $p$ prime and $n>1$. However, it will work nicely for just prime $p$.
Fri, 20 Jul 2012 12:09:03 -0500http://ask.sagemath.org/question/9166/polynomial-arithmetic-modulo-prime-powers/?answer=13837#post-id-13837Comment by calc314 for <p>Here is what I've found. You can define the coefficients in the ring <code>R=Integer(9)</code>. Then, define the polynomial ring <code>K.<x>=R[]</code>. After that, you can do calculations in the polynomial ring and can find the quotient and remainder. That handles the long division. See below.</p>
<pre><code>sage: R=Integers(9)
sage: list(R)
[0, 1, 2, 3, 4, 5, 6, 7, 8]
sage: K.<x>=R[]
sage: p1=x^4-3*x
sage: print p1
x^4 + 6*x
sage: p2=x^2+5
sage: p1*p2
x^6 + 5*x^4 + 6*x^3 + 3*x
sage: p1.quo_rem(p2)
(x^2 + 4, 6*x + 7)
sage: (x^2+4)*p2+(6*x+7)
x^4 + 6*x
</code></pre>
<p>In terms of factoring, I get an error, since $Z/p^nZ[x]$ is not an unique factorization domain, $n>1$.</p>
<pre><code>sage: p1.factor()
Traceback (most recent call last):
...
NotImplementedError: factorization of polynomials over rings with composite characteristic is not implemented
</code></pre>
<p>So this won't work for $p^n$ with $p$ prime and $n>1$. However, it will work nicely for just prime $p$.</p>
http://ask.sagemath.org/question/9166/polynomial-arithmetic-modulo-prime-powers/?comment=19370#post-id-19370One more note...since $Z/9Z$ is not an integral domain, `quo_rem` won't always work. For example, `(x^2).quo_rem(3*x)` does not work in the polynomial ring set up above.Fri, 20 Jul 2012 18:08:10 -0500http://ask.sagemath.org/question/9166/polynomial-arithmetic-modulo-prime-powers/?comment=19370#post-id-19370