Editing Polynomial ring (section)

=== Factorization ===
{{main|Polynomial factorization}}

Except for factorization, all previous properties of {{math|''K''[''X'']}} are [[effective proof|effective]], since their proofs, as sketched above, are associated with [[algorithm]]s for testing the property and computing the polynomials whose existence are asserted. Moreover these algorithms are efficient, as their [[computational complexity]] is a [[quadratic time|quadratic]] function of the input size.

The situation is completely different for factorization: the proof of the unique factorization does not give any hint for a method for factorizing. Already for the integers, there is no known algorithm running on a classical (non-quantum) computer for factorizing them in [[polynomial time]]. This is the basis of the [[RSA cryptosystem]], widely used for secure Internet communications.

In the case of {{math|''K''[''X'']}}, the factors, and the methods for computing them, depend strongly on {{mvar|K}}. Over the complex numbers, the irreducible factors (those that cannot be factorized further) are all of degree one, while, over the real numbers, there are irreducible polynomials of degree 2, and, over the [[rational number]]s, there are irreducible polynomials of any degree. For example, the polynomial <math>X^4-2</math> is irreducible over the rational numbers, is factored as <math>(X - \sqrt[4]2)(X+\sqrt[4]2)(X^2+\sqrt 2)</math> over the real numbers and, and as <math>(X-\sqrt[4]2)(X+\sqrt[4]2)(X-i\sqrt[4]2)(X+i\sqrt[4]2)</math> over the complex numbers.

The existence of a factorization algorithm depends also on the ground field. In the case of the real or complex numbers, [[Abel–Ruffini theorem]] shows that the roots of some  polynomials, and thus the irreducible factors, cannot be computed exactly. Therefore, a factorization algorithm can compute only approximations of the factors. Various algorithms have been designed for computing such approximations, see [[Root finding of polynomials]].

There is an example of a field {{math|''K''}} such that there exist exact algorithms for the arithmetic operations of {{math|''K''}}, but there cannot exist any algorithm for deciding whether a polynomial of the form <math>X^p - a</math> is [[irreducible polynomial|irreducible]] or is a product of polynomials of lower degree.<ref>{{citation |author1=Fröhlich, A.|author2=Shepherson, J. C.|title = On the factorisation of polynomials in a finite number of steps|journal = Mathematische Zeitschrift|volume = 62|issue=1|year = 1955|issn = 0025-5874|doi=10.1007/BF01180640|pages=331–334|s2cid=119955899 }}</ref>

On the other hand, over the rational numbers and over finite fields, the situation is better than for [[integer factorization]], as there are [[factorization of polynomials|factorization algorithm]]s that have a [[polynomial complexity]]. They are implemented in most general purpose [[computer algebra system]]s.