Faktorizace v matematice a jejích aplikacích označuje problém rozložení objektu na součin, v nejčastější podobě pak rozklad celého čísla na součin prvočísel. Například číslo 15 lze napsat jako součin 3 · 5. Obecněji lze rozkládat i jiné algebraické objekty, např. polynom druhého řádu x² − 4 lze vyjádřit jako součin dvou polynomů prvního řádu (x − 2)(x + 2).
Rozklad celého čísla na prvočinitele je složitá úloha a na její nezvládnutelnosti pro dostatečně velká čísla jsou založeny některé kryptografické metody, např. algoritmus RSA pro šifrování s veřejným klíčem.
Faktorizace celých čísel
Podle základní věty aritmetiky lze libovolné celé číslo jednoznačně rozložit na součin prvočísel. Pro takovou úlohu s velkými čísly však není znám žádný efektivní algoritmus a předpokládá se, že ani neexistuje. V současné době není známa přesná klasifikace této úlohy do tříd složitosti, nejlepší algoritmy mají sub-exponcionální časovou složitost.
Je známo, že rozhodovací verze „má číslo N nějakého činitele menšího než M?“ patří do NP i co-NP (odpovědi ANO i NE lze ověřit na Turingově stroji v polynomiálním čase). Předpokládá se, že faktorizace celých čísel není prvkem tříd P, NP-complete a co-NP-complete.. See in particular p. 583.
Zdánlivě podobná úloha, test prvočíselnosti, „je N číslem složeným“ (či ekvivalentně: „je N prvočíslem“) má polynomiální složitost.
Odkazy
Reference
Související články Základní věta algebry
Kategorie:Aritmetika