structural:reformatting
Factorization

Except for factorization, all previous properties of K are effective, since their proofs, as sketched above, are associated with algorithms for testing the property and computing the polynomials whose existence are asserted. Moreover these algorithms are efficient, as their computational complexity is a 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 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 K, the factors, and the methods for computing them, depend strongly on 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 numbers, there are irreducible polynomials of any degree. For example, the polynomial X 4 − 2 {\displaystyle X^{4}-2} is irreducible over the rational numbers, is factored as (X − 2 4) (X + 2 4) (X 2 + 2) {\displaystyle (X-{\sqrt{2}})(X+{\sqrt{2}})(X^{2}+{\sqrt {2}})} over the real numbers and, and as (X − 2 4) (X + 2 4) (X − i 2 4) (X + i 2 4) {\displaystyle (X-{\sqrt{2}})(X+{\sqrt{2}})(X-i{\sqrt{2}})(X+i{\sqrt{2}})} 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 K such that there exist exact algorithms for the arithmetic operations of K, but there cannot exist any algorithm for deciding whether a polynomial of the form X p − a {\displaystyle X^{p}-a} is irreducible or is a product of polynomials of lower degree.

On the other hand, over the rational numbers and over finite fields, the situation is better than for integer factorization, as there are factorization algorithms that have a polynomial complexity. They are implemented in most general purpose computer algebra systems.