Faktorizace: Porovnání verzí

Podle [[základní věta aritmetiky|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řída složitosti|tříd složitosti]], je však známo, že (přesněji rozhodovací verze faktorizace – „má číslo ''N'' nějakého činitele menšího než ''M''?“) patří do [[NP (třída složitosti)|NP]] i [[co-NP]] (odpovědi ANO i NE lze ověřit v polynomiálním čase).