Jako faktorizace se v teorii čísel označuje problém rozložení čísla na součin menších čísel, 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 považován za velmi těžkou úlohu a na její nezvládnutelnosti pro velká čísla jsou založeny některé kryptografické metody, např. algoritmus RSA pro šifrování s veřejným klíčem.^[1]

Ne všechna celá čísla lze rozdělit na prvočinitele. Ty, které nelze, jako např. 3, 5, 7, 11, 13, ..., 2²¹⁶⁰⁹¹-1 jsou právě prvočísla. Prvočísla jsou jak pro informatiky, tak i pro matematiky velmi fascinujícími objekty. Existují i vědní obory, které hledají nová prvočísla a snaží se najít nové či vylepšit stávající postupy pro rychlejší faktorizaci velkých čísel.^[2]

^[1] 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, 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 i co-NP (odpovědi ANO i NE lze ověřit v polynomiálním čase). Předpokládá se, že padá mimo třídy P, NP-complete a co-NP-complete. Zajímavé je, že zdánlivě podobná úloha „je N číslo složené“ (či ekvivalentně: „je N prvočíslo“) je zřejmě mnohem jednodušší: bylo dokázáno, že ji lze vyřešit v polynomiálním čase. [Zdroj: wikipedia.org]

^[2] http://primes.utm.edu/