Support non-primepower modulus for the polynomial factorization calculator
Opened this issue · 5 comments
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.
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.
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.
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.
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")
In the case that there is no unique factorization, you can try to let the calculator return all possible factorizations.