Polynomials, Constructivity and Randomness

We discuss some effective characterizations of the prime elements in a polynomial ring and polynomial factorization techniques. We emphasize that some factorization methods are probabilistic, their efficiency justifies the experimental trend in mathematics. The possibility of an effective version of Hilbert's irreducibility theorem and the probabilistic techniques of Berlekamp will be also discussed. Finally, bounds on the heights of integer polynomials are used as tools for improving polynomial factorizations. 1 C. Calude (ed.). The Finite, the Unbounded and the Infinite, Proceedings of the Summer School "Chaitin Complexity and Applications", Mangalia, Romania, 27 June - 6 July, 1995