support factoring polynomials modulo prime powers

[yyyyx4]

Currently, Polynomial_zmod_flint refuses to factor polynomials modulo composites, which is generally not well-defined. However, we can easily make this work modulo prime powers (where it is well-defined) by reusing the implementation for polynomials over p‑adics. This is almost certainly not the fastest way of doing it, but at least it works.

Component: algebra

Author: Lorenz Panny

Branch/Commit: 19018bb

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/34371

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:2

It probably would be too much trouble to separate out the algorithm into a separate function rather than converting the elements by changing the base ring. If it is actually simple, then please do so. Otherwise, green bot => positive review.

[yyyyx4]

comment:3

The implementation for ℤₚ[x] relies on PARI, whereas the implementation of (ℤ/n)[x] is based on FLINT. I suppose we could inline the PARI conversion and call PARI without explicitly changing to ℤₚ, but that's already much more effort than this and I'm not sure how much it would actually help (it saves some Python overhead, but the conversion is still needed).

Personally I'd argue that this is an easy way to make something work that didn't work previously, and we can improve the performance later if it turns out to be a problem.

[tscrim]

comment:4

Replying to @yyyyx4:

The implementation for ℤₚ[x] relies on PARI, whereas the implementation of (ℤ/n)[x] is based on FLINT. I suppose we could inline the PARI conversion and call PARI without explicitly changing to ℤₚ, but that's already much more effort than this and I'm not sure how much it would actually help (it saves some Python overhead, but the conversion is still needed).

It also means you get an additional transient object that takes up time and memory, which could matter if the polynomial is "big". However...

Personally I'd argue that this is an easy way to make something work that didn't work previously, and we can improve the performance later if it turns out to be a problem.

I agree fully. Only to be done if it was clearly easy.

[vbraun]

Changed branch from public/polynomial_factorization_modulo_prime_powers to 19018bb