Factoring polynomials over IntegerModRings

asked 2011-07-03 23:17:48 +0100

Anonymous

updated 2015-01-13 21:46:11 +0100

FrédéricC

5206 ●3 ●43 ●114

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.

Comments

answered 2011-07-03 23:50:30 +0100

Mike Hansen

4088 ●24 ●48 ●90

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

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 ( 2011-07-04 00:30:00 +0100 )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 ( 2011-07-04 01:20:33 +0100 )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 ( 2011-07-05 04:34:18 +0100 )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 ( 2014-12-26 15:02:54 +0100 )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 ( 2015-02-22 03:54:01 +0100 )edit

add a comment

Your Answer

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

Factoring polynomials over IntegerModRings

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Factoring polynomials over IntegerModRings edit

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Factoring polynomials over IntegerModRings