faktoriatsioon

Faktoriatsioon on matemaatiline protsess, mille käigus objekt esitatakse kui korrutiste kogum, mille tegurid on selle korrutise koostisosad. See mõiste kehtib nii täisarvude kui ka polünoomide puhul ning hõlmab nii lihtsaid jaotusi kui ka keerukamaid faktoriatsioonimeetodeid.

Täisarvude faktoriatsioon

Täisarvude puhul on oluline primfaktoratsioon: iga arv n > 1 võib esitada kui korrutis primide ehk primfaktoridena, näiteks n = p1^a1 p2^a2 …, kus pi on primid ja ai on mittenegatiivsed täisarvud. Selline esitus on unikaalne, välja arvatud tegurite järjekord. Näide: 60 = 2^2 · 3 · 5.

Polünoomide faktoriatsioon

Polünoomide korral tähendab faktoriatsioon f(x) jagamist produktiks polünoomidest, mida ei saa veel edasi jagada. Näide: x^2 - 5x + 6 = (x-2)(x-3). Üldine eesmärk on leida polünoomi maksimaalselt mitteintegratsiooniga tegurid.

Meetodid

Faktoriatsioonile on erinevaid meetodeid. Täisarvude puhul kasutatakse lihtsat proovijagamist ning suuremate arvude haaramiseks ka keerukamaid algoritme (nt ECM, GNFS või Pollard's rho). Polünoomide faktoratsiooni puhul rakendatakse meetodeid nagu rationaalsete juurte teoreem, Berlekampi meetod, Cantor–Zassenhaus ja teised sõltuvalt alusväljast.

Rakendused ja ajalugu

Faktoriatsioon on oluline number­teoorias ja algebra, ning selle mõiste alusel toimivad paljud algoritmid ja rakendused, sealhulgas krüptograafia (nt RSA). Ajaloos on teemat uuritud alates antiikajast ning see on arenenud nii teooria kui ka praktiliste meetodite vallas.