Factorization is the process of expressing a mathematical object as a product of simpler elements. In elementary arithmetic this means writing an integer as the product of two or more smaller integers; in algebra it means expressing a polynomial as a product of lower-degree polynomials. The resulting pieces are called factors or divisors and are useful for simplification, solving equations, and understanding structural properties.

Basic concepts and terminology

An integer greater than 1 that is not prime is called a composite number. A factor (or divisor) of an integer n is any integer that divides n without leaving a remainder; 1 and n are always factors, and factors other than n are often called proper divisors. When the factors cannot be further broken into nontrivial factors, they are called irreducible or, in the integer case, prime numbers. See also a general discussion of divisors for related terminology.

Prime factorization and the fundamental theorem

Prime factorization is the expression of an integer as a product of prime numbers. The Fundamental Theorem of Arithmetic states that every integer greater than 1 has a unique prime factorization, up to the order of the factors. For example, 12 = 3 × 2 × 2, often written 12 = 2^2 × 3; and 72 = 2 × 2 × 2 × 3 × 3, commonly written 72 = 2^3 × 3^2. Because 1 is not prime, it does not appear in prime factorizations. The uniqueness of prime factorization underpins many theoretical and practical results in number theory.

Algorithms and computational aspects

Factorization methods range from simple to sophisticated. For small numbers, trial division (testing divisibility by small primes) is straightforward. More advanced classical algorithms include wheel factorization, Pollard's rho algorithm, the quadratic sieve, and the general number field sieve (GNFS), which is the most efficient known classical method for large, arbitrary integers. On the other hand, quantum algorithms such as Shor's algorithm can factor integers in polynomial time on a sufficiently large quantum computer, a capability that would change the practical security of many contemporary cryptosystems.

Polynomial factorization

Factorization also applies to polynomials: expressing a polynomial as a product of lower-degree polynomials with coefficients in a chosen ring or field. For example, x^2 - 1 factors over the rationals as (x - 1)(x + 1). A polynomial that cannot be factored further (relative to the coefficient field) is called irreducible. Algorithms for polynomial factorization include Berlekamp's algorithm and the Cantor–Zassenhaus algorithm for finite fields, and various methods based on gcd computations and root-finding over larger fields.

Applications and notable facts

  • Cryptography: The practical difficulty of factoring very large integers is the security basis for RSA and related schemes; see applications to cryptography.
  • Arithmetic simplification: Factorization is used to simplify fractions, compute greatest common divisors, and solve Diophantine equations.
  • Algebra and number theory: Unique factorization generalizes to other settings (for example, unique factorization domains) and its failure in some rings motivates deeper study in algebraic number theory.
  • Distinctions: Factoring integers into primes differs from factoring polynomials into irreducible factors; the base ring (integers, rationals, finite fields) determines which factors are allowed and whether a factorization exists in that form.

Examples and further reading

Some simple examples illustrate the ideas: the integer 30 has prime factorization 2 × 3 × 5, while 28 = 2 × 2 × 7 = 2^2 × 7. The polynomial x^2 + 1 is irreducible over the rationals but factors over the complex numbers as (x + i)(x - i). For definitions of terms used here, including what constitutes a prime and how divisors behave in different rings, consult standard references in elementary number theory and abstract algebra. For computational methods and practical tools, many textbooks and algorithm surveys describe the algorithms mentioned above in greater detail; see additional resources at composite number discussions and divisor references.