# Ticket #12561(new enhancement)

Opened 15 months ago

Reported by: Owned by: bsinclai roed major sage-5.10 padics roed N/A Brian Sinclair, Sebastian Pauli

### Description

A native sage implementation of padic polynomial factoring

## Change History

### comment:1 Changed 4 months ago by saraedum

On the wiki page about padic factoring it says that the implementation doesn't work correctly for some examples. Is there only a problem with some specific cases? I just tried a few products of low degree polynomials and the factorizations seemed ok.

I want to try to debug the code, so if you know of any simple examples for which it doesn't work, that would be helpful.

### comment:2 Changed 4 months ago by bsinclai

Other than the poor state of documentation and polish, I cannot find any faults. I have run the code through all of the previously failed examples with no issue outside of occasionally having insufficient precision. The newton polygon code does not elegantly handle the infinite slope case (the case where the current phi actually divides Phi), but it doesn't have to for factoring since it can be (and is) caught earlier in the loop.

### comment:3 follow-up: ↓ 4 Changed 3 months ago by spice

Patch applies correctly on 7.5 and all doctests written so far pass. However:

In the doctest from pfactortree():

```sage: from sage.rings.polynomial.padics.factor.factoring import jorder4,pfactortree
sage: f = ZpFM(2,24,'terse')['x']( (x^32+16)*(x^32+16+2^16*x^2)+2^34 )
sage: pfactortree(f) # long (3.8s)
[(1 + O(2^24))*x^64 + (65536 + O(2^24))*x^34 + (32 + O(2^24))*x^32 + (1048576 + O(2^24))*x^2 + (256 + O(2^24))]
```

This is just returning the polynomial unfactored, so demonstrably the factoring isn't working here. We should get:

```sage: f = ZpFM(2,24,'terse')['x']( (x^32+16)*(x^32+16+2^16*x^2)+2^34 )
sage: f.factor()
((1 + O(2^24))*x^32 + (65536 + O(2^24))*x^2 + (16 + O(2^24))) * ((1 + O(2^24))*x^32 + (16 + O(2^24)))
```

Also, we should rework this code so that a sage Factorization object is returned, and that pfactortree is called by the .factor() method attached to p-adic polynomials.

### comment:4 in reply to: ↑ 3 Changed 3 months ago by roed

Patch applies correctly on 7.5 and all doctests written so far pass. However:

In the doctest from pfactortree():

```sage: from sage.rings.polynomial.padics.factor.factoring import jorder4,pfactortree
sage: f = ZpFM(2,24,'terse')['x']( (x^32+16)*(x^32+16+2^16*x^2)+2^34 )
sage: pfactortree(f) # long (3.8s)
[(1 + O(2^24))*x^64 + (65536 + O(2^24))*x^34 + (32 + O(2^24))*x^32 + (1048576 + O(2^24))*x^2 + (256 + O(2^24))]
```

This is just returning the polynomial unfactored, so demonstrably the factoring isn't working here. We should get:

```sage: f = ZpFM(2,24,'terse')['x']( (x^32+16)*(x^32+16+2^16*x^2)+2^34 )
sage: f.factor()
((1 + O(2^24))*x^32 + (65536 + O(2^24))*x^2 + (16 + O(2^24))) * ((1 + O(2^24))*x^32 + (16 + O(2^24)))
```

Also, we should rework this code so that a sage Factorization object is returned, and that pfactortree is called by the .factor() method attached to p-adic polynomials.

Note that increasing the precision yields a factorization:

```sage: f = ZpFM(2,44,'terse')['x']( (x^32+16)*(x^32+16+2^16*x^2) + 2^34)
sage: pfactortree(f)
[(1 + O(2^44))*x^32 + (7242791239680 + O(2^44))*x^30 + (13194407968768 + O(2^44))*x^28 + (7902202888192 + O(2^44))*x^26 + (2147483648 + O(2^44))*x^24 + (442381107200 + O(2^44))*x^22 + (21474836480 + O(2^44))*x^20 + (6193337597952 + O(2^44))*x^18 + (240518168576 + O(2^44))*x^16 + (2405122965504 + O(2^44))*x^14 + (2886218022912 + O(2^44))*x^12 + (16766847680512 + O(2^44))*x^10 + (1099511627776 + O(2^44))*x^8 + (2190164885504 + O(2^44))*x^6 + (14293651161088 + O(2^44))*x^4 + (14178492350464 + O(2^44))*x^2 + (8796093022224 + O(2^44)),
(1 + O(2^44))*x^32 + (10349394804736 + O(2^44))*x^30 + (8796093022208 + O(2^44))*x^28 + (5291936645120 + O(2^44))*x^26 + (17149804937216 + O(2^44))*x^22 + (11398848446464 + O(2^44))*x^18 + (15187063078912 + O(2^44))*x^14 + (825338363904 + O(2^44))*x^10 + (15402021158912 + O(2^44))*x^6 + (3413693759488 + O(2^44))*x^2 + (8797166764048 + O(2^44))]
```

In the case Simon pointed out, adding 2^34 doesn't do anything since the precision cap of the base ring is 24, so we have an actual example of a reducible polynomial being claimed to be irreducible.

Note: See TracTickets for help on using tickets.