Support non-primepower modulus for the polynomial factorization calculator

[xayahrainie4793]

Currently the modulus of the polynomial factorization calculator must be a prime number or a power of a prime, but I think that a general composite number modulus should be possible, e.g. for a polynomial mod 391, you can solve this polynomial with mod 17 and mod 23, thus I think that the polynomial factorization calculator can also support non-primepower modulus.

[alpertron]

Yes, you are right. I could use the Chinese Remainder Theorem to get the results you request. I will try to work on that when I have time.

[alpertron]

This could be more difficult when the polynomial mod pq has a factor with degree A, but that polynomial can be decomposed in 3 polynomials of degrees B, C and D mod p and 2 polynomials of degrees E and F mod q, where A = B + C + D = E + F.

[alpertron]

The most difficult issue when trying to factor polynomial modulo a composite number, is that there is no unique factorization.

So the idea will be not to find polynomial factorizations but only the roots.

[xayahrainie4793]

This also holds (i.e. there is no unique factorization) for the true prime power (i.e. prime powers with exponents > 1) modulus, e.g. factor the polynomial x^2-1 mod 8, it can be (x-1)*(x+1) or (x-3)*(x+3), but currently it already supports the true prime power (i.e. prime powers with exponents > 1) modulus (although I cannot calculate "factor the polynomial x^2-1 mod 8", it returns "Cannot lift because of duplicate factors modulo prime")

[xayahrainie4793]

In the case that there is no unique factorization, you can try to let the calculator return all possible factorizations.