Faktorizácia

Faktorizácia alebo rozklad na činitele je v matematike a jej aplikáciách problém rozloženia čísla na súčin menších čísel, v najbežnejšej podobe je to rozklad celého čísla na súčin prvočísel. Napríklad číslo 15 je možné zapísať ako súčin 3 ⋅ 5. Všeobecnejšie je možné rozkladať aj iné algebrické objekty, napríklad polynóm druhého stupňa x² − 4 je možné vyjadriť ako súčin dvoch polynómov prvého stupňa (x − 2)(x + 2).

Rozklad celého čísla na prvočinetele je považovaný za veľmi ťažkú úlohu a na jej nezvládnutí pre veľké čísla sú založené niektoré kryptografické metódy, napríklad algoritmus RSA na šifrovanie s verejným kľúčom.

Faktorizácia celých čísel

Podľa základnej vety aritmetiky možno každé celé číslo jednoznačne rozložiť na súčin prvočísel. Pre takúto úlohu s veľkými číslami však nie je známy žiadny efektívny algoritmus a predpokladá sa, že ani neexistuje. V súčasnosti nie je známa presná klasifikácia tejto úlohy do tried zložitosti, je však známe, že rozhodovacia verzia faktorizácie – „má číslo N nejaký činiteľ menší než M?“ patrí do NP i co-NP (odpovede ÁNO i NIE možno overiť v polynomiálnom čase).

Predpokladá sa, že patrí mimo triedy P, NP-complete a co-NP-complete.

Zaujímavé je, že zdanlivo podobná úloha „je N číslo zložené“ (či ekvivalentne: „je N prvočíslo“) je zrejme omnoho jednoduchšia: bolo dokázané, že ju možno vyriešiť v polynomiálnom čase.