A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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.[1]
Referencie
- ↑ . Faktorizacia . Bratislava: . Dostupné online.
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk