Ask Your Question

Polynomial arithmetic modulo prime powers

asked 2012-07-20 07:37:12 -0500

Robert Pollack gravatar image

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??

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted

answered 2012-07-20 12:09:03 -0500

calc314 gravatar image

updated 2012-07-20 12:55:13 -0500

Here 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$.

edit flag offensive delete link more


One 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.

calc314 gravatar imagecalc314 ( 2012-07-20 18:08:10 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2012-07-20 07:37:12 -0500

Seen: 866 times

Last updated: Jul 20 '12