A matematikában a faktorizáció egy objektum (például egy szám , egy polinom vagy egy mátrix ) lebontása más objektumok vagy tényezők szorzatára , amelyek szorzásakor az eredeti objektumot adják. Például a 15-ös számú tényezőt a 3-as és 5-ös prímszámokba , az x 2 − 4 polinomot pedig az ( x -2)( x + 2)-be. A faktorizálás eredményeként minden esetben az eredetinél egyszerűbb objektumok szorzatát kapjuk.
A faktorizálás célja, hogy egy objektumot "alapvető építőelemekké" redukáljon, például egy számot prímszámokká, egy polinomot irreducibilis polinomokká . Az egész számok faktorizálását az aritmetika alaptétele , a polinomokét pedig az algebra alaptétele biztosítja .
A faktorálási polinomok ellentéte a kibővítésük , a polinomtényezők szorzása, hogy egy "kibővített" polinomot kapjunk, amely kifejezések összegeként van írva.
Az egész számok faktorizálása nagy számokra igen nehéz feladat. Nincs ismert módja ennek a probléma gyors megoldásának. Bonyolultsága bizonyos nyilvános kulcsú titkosítási algoritmusok , például az RSA mögött áll .
A mátrix egy speciális mátrixtermékké is alakítható olyan alkalmazásokhoz, ahol ez a forma kényelmes. Ennek egyik fő példája az ortogonális , unitárius és háromszög mátrixok használata. Számos módja van a faktorizálásnak: QR dekompozíció , LQ , QL , RQ , RZ .
Egy másik példa a függvények faktorizálása más , bizonyos tulajdonságokkal rendelkező függvények összetételeként . Például minden függvény egy szürjektív függvény és egy injektív függvény összetételének tekinthető . Ez a megközelítés a rendszerek faktorizációs koncepciójának általánosítása.
Végül a gráfelméletben a gráffaktorizációt úgy definiáljuk, mint egy gráf felbontását egy speciális alakú, él-diszjunkt átívelő részgráfokra (vagyis a gráf összes csúcsát tartalmazó részgráfokra) [1] .
Az aritmetika alaptétele szerint minden természetes szám egyedi prímtényezőkké alakítható. Számos egészszámú faktorizációs algoritmus létezik, amellyel bármely természetes szám rekurzív képletekkel faktorizálható a prímtényezőinek összetételére . Nagyon nagy számok esetén azonban még nem ismert hatékony algoritmus.
A Gauss-számok gyűrűje faktoriális , vagyis a prímtényezőkre való felosztás a sorrendjükig és az asszociációjukig egyedi ( az egység osztóival való szorzás ).