This article is about the mathematical concept. Are you looking for Factoring?

In mathematics, factorization or factoring is the decomposition of an object (for example, a number, a polynomial, or a matrix) into a product of other objects, or factors, which when multiplied together give the original. For example, the number 15 factors into primes as 3 × 5; and the polynomial x² − 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 polynomials. 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 matrix can also be factorized into a product of matrices of special types, for an application in which that form is convenient. One major example of this uses an orthogonal or unitary matrix, and a triangular matrix. There are different types: QR decomposition, LQ, QL, RQ, RZ.

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 unifiable 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

External links

• A page about factorisation, Algebra, Factoring (http://library.thinkquest.org/20991/alg/factoring.html?tqskip1=1)
• WIMS Factoris (http://wims.unice.fr/wims/wims.cgi?module=tool/algebra/factor.en) is an online factorization tool.

de:Primfaktorzerlegung is:Þáttun it:Fattorizzazione pl:Faktoryzacja sv:faktorisering zh:因数分解