: This article is about the mathematical concept. For the financial term see Factoring (trade).

In mathematics, factorization or factoring is the decomposition of an object (for example, a number, a polynomial, or a matrix) into a multiplication of other objects, or factors, which when multiplication together give the original. For example, the number 15 factors into prime number as 3 × 5; and the polynomial x 2 − 4 factors as ( x − 2)( x + 2). In both cases, we obtain a product of simpler things.

The aim of factoring is usually to reduce something to basic building blocks , such as numbers to prime numbers, or polynomials to irreducible polynomial. Factoring integers is covered by the fundamental theorem of arithmetic and factoring polynomials by the fundamental theorem of algebra.

Integer factorization for large integers appears to be a difficult problem. There is no known method to carry it out quickly. Its complexity is the basis of the assumed security of some public key cryptography algorithms, such as RSA.

A , LQ, QL, RQ, RZ.

Another example is the factorization of a function (mathematics) as the function composition of other functions having certain properties; for example, every function can be viewed as the composition of a surjective function with an injective function.

=Factoring in mathematical logic=

In mathematical logic and automated theorem proving, factoring is the technique of deriving a single, more specific atom from a disjunction of two more general unification atoms. For example, from ∀ X , Y : P ( X , a ) or P ( b , Y ) we can derive P ( b , a ).

=See also=

*Prime factorization algorithm *Program synthesis *Unique factorization

=External links=