Faktorizálása

Faktorizálása olyan matematikai művelet, amely egy objektumot olyan tényezőkre bont, amelyek szorzata adja az eredetit, és amelyek a megadott gyűrűben vagy testben nem bonthatók tovább. A kifejezés általában két fő kontextusban használatos: egész számokra vonatkozó prímfaktorizálás és polinomokra vonatkozó tényezőkre bontás.

Egész számoknál a faktorizálás során egy n > 1 számot prímek szorzataként adunk meg: n = p1 · p2 · ... · pk. A sorrend és a megismétlődés nem számít; az egyediséget az aritmetika fundamentális tétele biztosítja. Gyakorlati módszerek közé tartozik a próbavágás, keret (wheel) módszerek, és fejlettebb algoritmusok, például a Pollard-féle rho vagy az elliptikus görbe faktorizáció.

Polinomok faktorizálása a megadott test felett történik: a polinomot olyan tényezőkre bontjuk, amelyeket irreducibilisnek tekintünk. A cél, hogy a polinomot a lehető legkisebb egységre, irreducibil tényezőkre bontsuk. Alapvető eszközök: a tartalom eltávolítása Gauss lemma alapján, a racionális gyök-tétel, és polinom gcd-jének használata. Speciális algoritmusok közé tartozik a Berlekamp-faktorizáció, Cantor–Zassenhaus-faktorizáció, valamint polinomok faktorizálása véges testeken.

Fontos szerepe van a számelméletben és a számítástudományban. Faktorizálás nélkül nehéz például olyan egyenleteket megoldani vagy egyszerűsíteni algebrai kifejezéseket. A gyakorlati alkalmazások közé tartozik a kriptográfia, ahol a számok prímfaktorálásának nehézsége alapja a biztonság (például RSA), valamint a számelméleti és algebrai szoftverek belső műveletei.