# Factoring polynomials over IntegerModRings

I'd like to factor efficiently polynomials over rings (more particularly the rings of the form IntegerModRing(n), other rings don't interest me right now). I've noticed that you can factor a polynomial differently when considering FIELDS, so that something like

factor(x^2-2, QQ[]) factor(x^2-2, RR[])

will output the different expected results. But what about

x = var('x') factor(x^5-x, IntegerModRing(25)['x'])?

What is actually outputted right now is

(x-1)(x+1)(x^2+1)*x

but the true factorization is x(x-1)(x+1)(x-7)(x+7)

(I computed it by hand, Sage couldn't do it.) Going for small numbers like 25 is easy but when I go for large numbers I get nasty codes if I try to compute that myself. Isn't there anyway to make the factor command factor those polynomials or another way to do it? Any suggestion is welcome.

I am new to Sage and I am beginning to love its features since I begin to study number theory and Sage has plenty of options for that purpose, but I must admit they are quite hard to understand since I am also new to Python, PARI, Magma... (not to programming though!) explanations in detail would be deeply appreciated.

edit retag close merge delete

( 2015-02-21 20:37:11 -0500 )edit

Sort by » oldest newest most voted

Actually, if you want to factor over a different base ring, you need to make the object you're trying to factor an element of that base ring. For example,

sage: factor(x^2+1)
x^2 + 1
sage: R.<x> = CC[]
sage: factor(x^2+1)
(x - I) * (x + I)
sage: R.<x> = IntegerModRing(5)[]
sage: factor(x^2+1)
(x + 2) * (x + 3)


Unfortunately, if you do it with IntegerModRing(25), we get a NotImplementedError.

sage: R.<x> = IntegerModRing(25)[]
sage: factor(x^2+1)
Traceback (most recent call last)
...
NotImplementedError: factorization of polynomials over rings with composite characteristic is not implemented

more

I noticed we can use the factor command over fields, but not over rings... that is why I am asking the question here : is there any way I could use an already built-in command of Sage I don't know to do it, or should I find an algorithm myself and use it for my sole purposes? Note that the IntegerModRing(5) is actually a field, not a ring, so I am not suprised there is no problem. (Actually a little, but less surprised than if you had found a way to make it mod 25..)

( 2011-07-03 17:30:00 -0500 )edit

Maybe one of the reasons it is not implemented is because of non-unicity of factorizations. Polynomials over fields are UFDs, which make factorization implementable... I think I'll just compute an algorithm myself. Thanks for the comment.

( 2011-07-03 18:20:33 -0500 )edit

There is indeed a problem with non uniqueness of factorizations. E.g., x^2 + 1 factorizes in ZZ/65ZZ[x] both as (x + 8)*(x + 57) and as (x + 18)*(x + 47).

( 2011-07-04 21:34:18 -0500 )edit

I do wonder this kind of a factorization over non UFDs, Hensel's Lemma says there is a unique factorization into "basic irreducible polynomials". Is there any command that allows us to get unique basic irreducible factorization of polynomials over Z_p^k?

( 2014-12-26 08:02:54 -0500 )edit

Unfortunately, even when you do use a field, K.<a> = GF(5**5, name='a') doesn't return a polynomial ring with this kind of factoring implemented - factor(a^2-1) won't work, there is no factor attribute.

( 2015-02-21 20:54:01 -0500 )edit