Faktorizácia

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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[upraviť | upraviť zdroj]

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.