Newton iteration is an almost 350-year-old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all roots simultaneously. In this form, the process yields better circuit complexity in the case when the number of rootsris small but the multiplicities are exponentially large. Our method sets up a linear system inrunknowns and iteratively builds the roots as formal power series. For an algebraic circuit\( f(x_1,\ldots ,x_n) \)of sizes, we prove that each factor has size at most a polynomial insand the degree of the squarefree part off. Consequently, if\( f_1 \)is a\( 2^{\Omega (n)} \)-hard polynomial, then any nonzero multiple\( \prod _{i} f_i^{e_i} \)is equally hard for arbitrary positive\( e_i \)’s, assuming that\( \sum _i\deg (f_i) \)is at most\( 2^{O(n)} \).It is an old open question whether the class of poly(n) size formulas (respectively, algebraic branching programs) is closed under factoring. We show that given a polynomialfof degree\( n^{O(1)} \)and formula (respectively, algebraic branching program) size\( n^{O(\log n)} \), we can find a similar-size formula (respectively, algebraic branching program) factor in randomized poly(\( n^{\log n} \)) time. Consequently, if the determinant requires an\( n^{\Omega (\log n)} \)size formula, then the same can be said about any of its nonzero multiples.In all of our proofs, we exploit the following property of multivariate polynomial factorization. Under a random linear transformation\( \tau \), the polynomial\( f(\tau \overline{x}) \)completely factors via power series roots. Moreover, the factorization adapts well to circuit complexity analysis. Therefore, with the help of the strong mathematical characterizations and the ‘allRootsNI’ technique, we make significant progress towards the old open problems; supplementing the vast body of classical results and concepts in algebraic circuit factorization (e.g., [17,51,54,111]).