Faktoryzacja liczby całkowitej polega na znalezieniu takich liczb całkowitych , że ich iloczyn jest równy danej liczbie: . Domyślnie żąda się nietrywialności rozkładu – tzn. aby żaden z czynników nie był równy ani , ani też nie był równy .
Złożoność obliczeniowa O ile mnożenie jest bardzo prostą czynnością, to nie są znane żadne szybkie (działające w czasie wielomianowym względem ilości cyfr rozkładanej liczby) metody faktoryzacji. Na złożoności obliczeniowej faktoryzacji opiera się system kryptografii asymetrycznej RSA.
Przykład: mając dwie liczby 65 537 i 65 539, można szybko je pomnożyć, uzyskując 4 295 229 443. Jednak rozłożenie 4 295 229 443 na czynniki jest trudne. Wszystkie znane algorytmy działają w czasie wykładniczym wobec długości rozkładanej liczby.
Algorytmy faktoryzacji Najprostsza metoda polega na próbie dzielenia faktoryzowanej liczby przez wszystkie liczby pierwsze od 2 do . Algorytm ten dobrze nadaje się do tego, żeby zacząć faktoryzować liczbę – losowa liczba ma zarówno małe, jak i duże czynniki. Połowa liczb dzieli się przez 2, co trzecia przez 3, co piąta przez 5 itd. Jeśli więc faktoryzowana liczba jest losowa, można z bardzo dużym prawdopodobieństwem pozbyć się szybko niskich czynników, po czym skończyć faktoryzację innym algorytmem.