Problem faktoryzacji jest przykładem zadania, w którym łatwo zweryfikować podane rozwiązanie przez pomnożenie czynników. Znalezienie takiego rozwiązania dla odpowiednio dobranych dużych liczb pozostaje jednak trudne dla znanych metod klasycznych. Dlatego faktoryzacja pojawia się zarówno w teorii złożoności, jak i w analizie założeń trudności obliczeniowej stosowanych w kryptografii.
Złożoność problemu W teorii złożoności wygodnie formułuje się faktoryzację jako problem decyzyjny. Dane są wtedy liczby naturalne i Pytanie brzmi, czy istnieje dzielnik taki, że i dzieli Odpowiedź „tak” można potwierdzić, podając odpowiedni czynnik. Odpowiedź „nie” można potwierdzić przez podanie rozkładu na czynniki pierwsze większe od i sprawdzenie ich pierwszości, na przykład przez test AKS.
Tak sformułowany problem należy do klas NP i co-NP, a także do bardziej restrykcyjnych klas związanych z jednoznacznymi certyfikatami. Nie wiadomo, czy należy do klasy P. Nie jest też znany jako problem NP-zupełny ani co-NP-zupełny. Dlatego często przedstawia się go jako kandydata na problem NP-pośredni. Dzięki algorytmowi Shora problem należy natomiast do kwantowej klasy BQP.