Związek z chińskim twierdzeniem o resztach Jeżeli jest iloczynem , to iterując wielomian modulo , tak naprawdę iterujemy go równolegle modulo i modulo . Zgodnie z chińskim twierdzeniem o resztach (CRT), istnieje izomorfizm pomiędzy pierścieniem a produktem pierścieni .
Oznacza to, że każda wartość w algorytmie odpowiada parze . Ponieważ (najmniejszy dzielnik) jest mniejszy od , zgodnie z paradoksem dnia urodzin ciąg wartości modulo zapętli się znacznie szybciej niż ciąg wartości modulo .
W momencie, gdy nastąpi kolizja modulo (czyli ), ale nie nastąpi jeszcze kolizja modulo (), różnica staje się wielokrotnością , ale nie wielokrotnością . Wówczas obliczenie skutecznie „wyłuskuje” czynnik .
Bibliografia
Rho Pollarda