Faktoreerida

Faktoreerida tähendab matemaatilise objekti väljendamist selle tegurite korrutisena. Tegurid on lihtsamad elemendid, mille korrutis annab algse objekti. Faktoreerimine kehtib nii arvude kui ka polünoomide kohta ning on oluline tööriist nii teoreetilises kui rakenduslikus matemaatikas, aidates mõista struktuuri, lihtsustada arvutusi ja tuvastada omadusi nagu primide esinemine või polünoomide irreduibiliteet.

Arvude faktoreerimine on protsess, mille käigus täisarv n > 1 esitatakse tegurite korrutisena. Tüüpiliselt kirjutatakse n = p1^a1 p2^a2 ... pk^ak, kus pi on eri primesid ja ai nende korrutised. Faktoreerimine on unikaalne järjestuse suhtes. Lihtsaim meetod on proovimine, kuid suurte arvude puhul kasutatakse tõhusaid meetodeid nagu Sieve of Eratosthenes väikeste tegurite leidmiseks ja seejärel keerukamaid meetodeid, näiteks Pollard’i rho või ECM. Täisarvude faktoreerimine on keskne teema krüptograafias, näiteks RSA-süsteemides, kus turvalisus põhineb suurte arvude faktoreerimise raskusel.

Polünoomide faktoreerimine tähendab polünoomi f(x) esitust kui korrutist g(x)h(x), mille deg g ja deg h on väiksemad kui deg f. Faktoreerimine toimub peamiselt polünoomide rõđkides nagu Z[x] või Q[x], kus polünoom on reducible, kui sellest saab jagada väiksemate polünoomide korrutisena. Gauss’i lemma toob seose Z[x] ja Q[x] vahel ning ütleb, et primitívpolünoom, mis jagub Q[x]-is, jagub ka Z[x]-is. Ratsionaalseid juuri aitab otsida Rational Root Theorem. Tõhusad algoritmid faktoreerimiseks hulgaliselt polünoomide jaoks hõlmavad Berlekampi ja Cantor–Zassenhause’i meetodeid ning Kaltofen’i meetodit suuremate polünoomide jaoks. Faktoreerimine kehtib ka polünoomide jaoks finite fieldidel F_q[x] ja teistes kontekstides.

Näited: 60 = 2^2 · 3 · 5; x^2 - 5x + 6 = (x - 2)(x - 3).