Brak znanego algorytmu wielomianowego nie jest dowodem jego nieistnienia. W literaturze podkreśla się raczej, że aktualna wiedza oddziela skuteczne testowanie pierwszości od znajdowania czynników. Pierwszość można rozstrzygać w czasie wielomianowym. Najlepsze znane algorytmy faktoryzacji ogólnego przeznaczenia mają natomiast czas podwykładniczy, ale nie wielomianowy.

Algorytmy faktoryzacji Algorytmy faktoryzacji można dzielić na metody specjalnego przeznaczenia i metody ogólnego przeznaczenia. Pierwsze wykorzystują szczególną postać rozkładanej liczby albo własności jednego z jej czynników. Drugie są projektowane tak, aby ich czas działania zależał przede wszystkim od rozmiaru samej liczby.

Metody specjalnego przeznaczenia sprawdza podzielność przez kolejne możliwe czynniki do pierwiastka z rozkładanej liczby. Jest wystarczające dla małych liczb i jako etap usuwania małych dzielników, ale staje się niepraktyczne, gdy liczba nie ma małych dzielników pierwszych.

Do metod specjalnego przeznaczenia należą również metoda Fermata, algorytm rho Pollarda, , , , oraz metody oparte na przedstawieniu liczby jako różnicy kwadratów.