Faktorizace

Faktorizace je matematická operace, která rozkládá objekt na součin jeho jednodušších faktorů. Nejčastěji se zmiňuje u čísel, polynomů a matic. U čísel jde o rozklad na prvočísla, u polynomů nad daným tělesem na součin irreducibilních polynomů a u matic na vhodný součin dalších matic, které usnadňují práci s daným objektem.

U čísel je klíčovou myšlenkou Základní věta aritmetiky: každý kladný celé číslo větší než 1 lze jedinečně vyjádřit jako součin prvočísel (řečeno až na uspořádání). Příkladem je 360 = 2^3 · 3^2 · 5. Praktické metody faktorování zahrnují prosté dělení, síť Eratosthenova na vyhledání prvočísel, a pokročilejší algoritmy jako Pollardovy metody či elliptic-curve factorization, které jsou důležité v kryptografii a číslo-teoretických výpočtech.

U polynomů se faktorizace týká zápisu polynomu jako součinu polynomů nižších stupňů. Nad tělesem lze využít teorie o irredibilních polynomech a algoritmů jako Cantor–Zassenhaus, Berlekamp či Kaltofen–Shoup. Cílem je získat rozklad do součinů lineárních nebo irreducibilních faktorů.

U matic se faktorizace používá k usnadnění lineárních operací a řešení soustav. Typické dekompozice zahrnují LU, PLU (s permutací), QR a singular value decomposition (SVD). Tyto rozklady umožňují řešit rovnice, určovat invertibilitu a provádět numerické analýzy.

Faktorizace má rozsáhlé aplikace v kryptografii, algoritmické algebře a numerických výpočtech.