Faktorizációk

Faktorizációk alatt olyan átalakításokat értünk, amelyek egy objektumot egyszerűbb tényezőkre bontanak. A fogalom széles körben használatos a matematikában és a kapcsolódó területeken: leggyakoribb értelemben az egész számok és polinomok faktorizációja, illetve a lineáris algebra különféle mátrixfaktorizációi. A faktorizációk célja általában a tulajdonságok jobb megértése és a számítások egyszerűsítése.

Egész számok faktorizációja: egy pozitív szám prímek szorzatára bontása. A prímtényező-szorzat egyedi sorrendtől független (a faktorizációt a fundamental arithmetic theorem biztosítja). Példa: 360 = 2^3 × 3^2 × 5. Nagy számok esetén a tényezőkre bontás nehéz feladat; széles körben alkalmazott algoritmusok közé tartozik a próbaosztás, a szita-alapú módszerek és a fejlettebb technikák, például a Pollard-féle rho, az ECM vagy a General Number Field Sieve. A faktorizáció nehézsége kulcsfontosságú a modern kriptográfiában, például az RSA biztonságában.

Polinomok faktorizációja: adott test felett a polinomokat irreducibilis tényezőkre bontjuk úgy, hogy a szorzatuk visszaadja az eredetit. Ha a koefficiensek egész vagy racionális számokból származnak, a Gauss–lemma segít abban, hogy a faktorizáció átvihető legyen Q[x]-re vagy Z[x]-re. Különféle algoritmusok léteznek modulusokon és véges testeken, például moduláris faktorizáció, Berlekamp–Cantor–Zassenhaus, illetve általános polinomfaktorizáció Kaltofen–Shoup-féle megközelítésekkel.

Mátrixok faktorizációja: lineáris algebrai alkalmazásokban gyakran beszélünk LU-, QR-, SVD-faktorizációkról vagy eigenérték-faktorizációkról, amelyek a lineáris rendszerek megoldását és a numerikus számításokat segítik.