Kaltofen [STOC 1986] gave a randomized algorithm to factor multivariate polynomials given by algebraic circuits. We derandomize the algorithm in some special cases. For an n-variate polynomial f of degree d from a class 𝒞 of algebraic circuits, we design a deterministic algorithm to find all its irreducible factors of degree ≤ δ, for constant δ. The running time of this algorithm stems from a deterministic PIT algorithm for class 𝒞 and a deterministic algorithm that tests divisibility of f by a polynomial of degree ≤ δ. By using the PIT algorithm for constant-depth circuits by Limaye, Srinivasan and Tavenas [FOCS 2021] and the divisibility results by Forbes [FOCS 2015], this generalizes and simplifies a recent result by Kumar, Ramanathan and Saptharishi [SODA 2024]. They designed a subexponential-time algorithm that, given a blackbox access to f computed by a constant-depth circuit, outputs its irreducible factors of degree ≤ δ. When the input f is sparse, the time complexity of our algorithm depends on a whitebox PIT algorithm for ∑_i m_i g_i^{d_i}, where m_i are monomials and deg(g_i) ≤ δ. All the previous algorithms required a blackbox PIT algorithm for the same class. Our second main result considers polynomials f, where each irreducible factor has degree at most δ. We show that all the irreducible factors with their multiplicities can be computed in polynomial time with blackbox access to f. Finally, we consider factorization of sparse polynomials. We show that in order to compute all the sparse irreducible factors efficiently, it suffices to derandomize irreducibility preserving bivariate projections for sparse polynomials.

Polynomial factoring has famous practical algorithms over fields-- finite, rational and p-adic. However, modulo prime powers, factoring gets harder because there is non-unique factorization and a combinatorial blowup ensues. For example, x^2+p \bmod p^2 is irreducible, but x^2+px \bmod p^2 has exponentially many factors! We present the first randomized poly(\deg f, łog p) time algorithm to factor a given univariate integral f(x) modulo p^k, for a prime p and k łeq 4. Thus, we solve the open question of factoring modulo p^3 posed in (Sircana, ISSAC'17). Our method reduces the general problem of factoring f(x) mod p^k to that of \em root finding in a related polynomial E(y) \bmodłangle p^k, \varphi(x)^\ell \rangle for some irreducible \varphi \bmod p. We can efficiently solve the latter for kłe4, by incrementally transforming E(y). Moreover, we discover an efficient refinement of Hensel lifting to lift factors of f(x) \bmod p to those \bmod\ p^4 (if possible). This was previously unknown, as the case of repeated factors of f(x) \bmod p forbids classical Hensel lifting.