JUCS - Journal of Universal Computer Science 2(5): 396-409, doi: 10.3217/jucs-002-05-0396
Polynomials, Constructivity and Randomness
expand article infoDoru Ştefănescu
‡ University of Bucharest, Bucharest, Romania
Open Access
Abstract
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.