# What is the best way to factor arbitrary polynomials

I am currently working on a Computer Algebra System and was wondering for suggestions on methods of finding roots/factors of polynomials. I am currently using the Numerical Durand-Kerner method but was wondering if there are any good non-numerical methods (primarily for simplifying fractions etc).

Ideally this should work for equations in multiple variables.

-
Into factors with... integer coefficients? There is a big Wikipedia article on that subject. – Qiaochu Yuan Jul 28 '10 at 0:32
Not necessarily - any unique factorisation into irreducible polynomials would do the job (I believe that the general formula of algebra states/implies that there should only be 1?). I have read multiple Wikipedia articles (wherein I found the Durand-Kerner method) around this subject but am looking for a more precise method. – ternaryOperator Jul 28 '10 at 1:48

If you are interested in the factorization algorithms employed in modern computer algebra systems such as Macsyma, Maple, or Mathematica, then see any of the standard introductions to computer algebra , e.g. Geddes et.al. "Algorithms for Computer Algebra"; Knuth, "TAOCP" v.2; von zur Gathen "Modern Computer Algebra"; Zippel "Effective Polynomial Computation". See also Kaltofen's surveys on polynomial factorization [116,68,56,7] in his publications list, which contains plenty of theory, history and literature references. Note: Kaltofen's home page appears to be temporarily down so instead see his paper [1] to get started (see comments)

1 Kaltofen, E. Factorization of Polynomials, pp. 95-113 in:
Computer Algebra, B. Buchberger, R. Loos, G. Collins, editors, Vienna, Austria, (1982).