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.
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.
This article uses material from the Wikipedia Slovenčina article Faktorizácia, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Obsah je dostupný pod licenciou CC BY-SA 4.0, pokiaľ nie je uvedené inak. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Slovenčina (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.