V matematice je faktorizace rozkladem objektu (například čísla , polynomu nebo matice ) na součin jiných objektů nebo faktorů , které, když se vynásobí , dávají původní objekt. Například číslo 15 se započítává do prvočísel 3 a 5 a polynom x 2 − 4 se započítává do ( x − 2)( x + 2). V důsledku faktorizace se ve všech případech získá součin jednodušších objektů, než byl původní.
Účelem faktorizace je redukovat objekt na „základní stavební bloky“, například číslo na prvočísla, polynom na neredukovatelné polynomy . Faktorizaci celých čísel poskytuje základní věta aritmetiky a polynomů základní věta algebry .
Opakem faktoringu polynomů je jejich rozšiřování , násobení polynomiálních faktorů k vytvoření "rozšířeného" polynomu zapsaného jako součet členů.
Faktorizace celých čísel na velká čísla je velmi obtížný úkol. Není znám žádný způsob, jak tento problém rychle vyřešit. Jeho složitost je základem některých šifrovacích algoritmů veřejného klíče , jako je RSA .
Matrici lze také rozložit na speciální druh matricového produktu pro aplikace, kde je tato forma vhodná. Jedním z hlavních příkladů je použití ortogonálních , unitárních a trojúhelníkových matic. Existují různé způsoby rozkladu: QR rozklad , LQ , QL , RQ , RZ .
Dalším příkladem je faktorizace funkcí jako složení jiných funkcí, které mají určité vlastnosti. Například každou funkci lze považovat za složení surjektivní funkce s injektivní funkcí . Tento přístup je zobecněním konceptu faktorizace systémů.
A konečně v teorii grafů je faktorizace grafu definována jako rozklad grafu na hranově disjunktní podgrafy (tj. podgrafy obsahující všechny vrcholy grafu) speciálního tvaru [1] .
Podle základního teorému aritmetiky má každé přirozené číslo jedinečnou rozklad na prvočinitele. Existuje mnoho celočíselných faktorizačních algoritmů , kterými lze nějaké přirozené číslo faktorizovat na složení jeho prvočísel pomocí rekurzivních vzorců . Pro velmi velká čísla však účinný algoritmus dosud není znám.
Okruh Gaussových čísel je faktoriál , to znamená, že rozklad na prvočinitele je jedinečný až do jejich pořadí a asociace (násobení děliteli jednoty ).