Polynomial factorization over modular ring

[chandra chowdhury]

Is it possible to factor polynomials completely over modular ring? 

Like 

x = var('x') 

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

gives

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

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

[Nils Bruin]

On Tuesday, August 15, 2017 at 7:21:03 AM UTC-7, chandra chowdhury wrote:

Is it possible to factor polynomials completely over modular ring? 

Like 

x = var('x') 

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

gives

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

The second argument is simply ignored here, by the looks of it

sage: factor(x^5-x,"moo")
(x^2 + 1)*(x + 1)*(x - 1)*x

You could file that as a (mild) bug.

Factorization of Z/25 directly isn't implemented:

sage: R=IntegerModRing(25)
sage: Rx.<x>=R[]
sage: factor(x^5-x)
NotImplementedError: factorization of polynomials over rings with composite characteristic is not implemented

Root finding is apparently implemented:

sage: (x^5-x).roots(multiplicities=False)
[0, 1, 7, 18, 24]

Alternatively, (beccause you're working mod a prime power) you could look at p-adic rings:

sage: R=Zp(5,2,"fixed-mod",print_mode="terse")
sage: Rx.<x>=R[]
sage: (x^5-x).factor()
((1 + O(5^2))*x + (1 + O(5^2))) * ((1 + O(5^2))*x + (7 + O(5^2))) * ((1 + O(5^2))*x + (18 + O(5^2))) * ((1 + O(5^2))*x + (24 + O(5^2))) * ((1 + O(5^2))*x + (0 + O(5^2)))

The "+O(5^2)" is a p-adic thing that would be nice to suppress here.
 

[John Cremona]

A relevant point, perhaps, is that polynomials over Z/25Z do not form
a unique factorization domain (or even a domain) so even the
definition of what factors you might want to see is unclear.
Following Nils, for a prime power modulus, a sensible definition is to
take an approximation of the p-adic factorization. The for a general
modulus the Chinese remainder theorem is probably relevant.

To illustrate my non-uniqueness point, modulo 8 we have x^2-1 =
(x+1)(x-1) = (x-3)(x+3).

John Cremona

>
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-support...@googlegroups.com.
> To post to this group, send email to sage-s...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/d/optout.

[Ralf Stephan]

On Tuesday, August 15, 2017 at 4:21:03 PM UTC+2, chandra chowdhury wrote:

x = var('x') 

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

Look at the output of `factor??`. A ring argument is not supported. So you have to create the ring first (var gives you only the symbolic ring). Then create the polynomial and can try to find out if it has a factor() method. After all this you may start to understand what the other posters were talking about.

Regards,