Ask Your Question
2

Factoring polynomials over IntegerModRings

asked 2011-07-03 16:17:48 -0500

anonymous user

Anonymous

updated 2015-01-13 14:46:11 -0500

FrédéricC gravatar image

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 flag offensive close merge delete

Comments

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

1 answer

Sort by » oldest newest most voted
1

answered 2011-07-03 16:50:30 -0500

Mike Hansen gravatar image

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
edit flag offensive delete link more

Comments

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

Patrick Da Silva gravatar imagePatrick Da Silva ( 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.

Patrick Da Silva gravatar imagePatrick Da Silva ( 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).

Francis Clarke gravatar imageFrancis Clarke ( 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?

algebraicallyclosed gravatar imagealgebraicallyclosed ( 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.

kcrisman gravatar imagekcrisman ( 2015-02-21 20:54:01 -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

Stats

Asked: 2011-07-03 16:17:48 -0500

Seen: 1,133 times

Last updated: Jul 03 '11