W najgorszym przypadku ( jest iloczynem dwóch liczb pierwszych podobnej wielkości, jak w RSA) algorytm ten zajmie bardzo dużo czasu.
Niektóre algorytmy opierają się na znajdowaniu takiej pary liczb i gdzie , , że:
Czyli albo , albo , albo ma wspólne dzielniki z oraz , a zatem sfaktoryzowaliśmy .
Najprostszą metodą tego typu jest sprawdzanie dla losowych liczb czy jest kwadratem (zwykłym, nie modulo). Można szybko znaleźć faktoryzację niektórych liczb, ale ogólnie metoda ta nie jest dużo lepsza od prób dzielenia.
O wiele lepszym sposobem jest wybranie zestawu małych liczb pierwszych i próby faktoryzacji kwadratów kolejnych losowanych liczb, używając tylko tych liczb pierwszych – jeśli faktoryzacja się nie powiedzie należy odrzucić wylosowaną liczbę, jeśli się powiedzie trzeba zachować i wykładniki:
a właściwie ich parzystości. Jeśli wybierze się zbyt duży zestaw liczb pierwszych, zwiększy to niepotrzebnie ilość obliczeń, jeśli wybierze zbyt mały – odrzuci zbyt dużo liczb.
Po uzbieraniu wystarczająco wielu relacji tego typu wybiera się taki podzbiór że wszystkie potęgi po prawej stronie są parzyste (dlatego nie zachowuje się dokładnych wykładników, a jedynie ich parzystości).