Computing all factorizations in ***
Howard Cheng, George Labahn · 2001
We present a new algorithm for determining all factorizations of a polynomial f in the domain ZN[x], a non-unique factorization domain, given in terms of parameters. From the prime factorization of N, the problem is reduced to factorization in Zph[x] where p is a prime and k ⪈ 1. If pk does not divide the discriminant of f and one factorization is given, our algorithm determines all factorizations with complexity Ο(n3 M(k log p)) where n denotes the degree of the input polynomial and M(t) denotes the complexity of multiplication of two t-bit numbers. Our algorithm improves on the method of von zur Gathen and Hartlieb, which has complexity Ο(n7 k(klog p + log n2). The improvement is achieved by processing all factors at the same time instead of one at a time and by computing the kernels and determinants of matrices over Zpk in an efficient manner.