Nie trzeba sprawdzać wszystkich możliwych zestawów – znalezienie właściwego jest relatywnie prostym problemem równoważnym odwracaniu macierzy.
Otrzymuje się wtedy:
gdzie to iloczyn odpowiednich a to iloczyn odpowiednich w potędze będącej połową sumy potęg dla znajdujących się po lewej stronie. Z prawdopodobieństwem 50% (dla będącego iloczynem 2 liczb) lub większym (dla mającego więcej czynników) liczby te są nietrywialną taką parą , . Jeśli tak nie jest, można próbować znaleźć inny zestaw liczb , których iloczyn ma parzyste wykładniki.
Większość zaawansowanych algorytmów rozkładu na czynniki pierwsze polega na znajdowaniu liczb o dobrych rozkładach w znacznie krótszym czasie.
Wielomiany
Faktoryzacja wielomianu to znalezienie takich wielomianów, że ich iloczyn jest równy danemu. W tym wypadku rozwiązanie nietrywialne nie może zawierać wielomianu o tym samym stopniu, co wielomian faktoryzowany. Zgodnie z zasadniczym twierdzeniem algebry dowolny wielomian o stopniu nad ciałem liczb zespolonych można rozłożyć na iloczyn wielomianów 1.