Как я могу улучшить алгоритм Rho этого Полларда для обработки продуктов полубольших простых чисел?

Ниже моя реализация алгоритма rho Полларда для простой факторизации:

#include <vector>
#include <queue>

#include <gmpxx.h>

// Interface to the GMP random number functions.
gmp_randclass rng(gmp_randinit_default);

// Returns a divisor of N using Pollard's rho method.
mpz_class getDivisor(const mpz_class &N)
{
mpz_class c = rng.get_z_range(N);
mpz_class x = rng.get_z_range(N);
mpz_class y = x;
mpz_class d = 1;
mpz_class z;

while (d == 1) {
x = (x*x + c) % N;
y = (y*y + c) % N;
y = (y*y + c) % N;
z = x - y;
mpz_gcd(d.get_mpz_t(), z.get_mpz_t(), N.get_mpz_t());
}

return d;
}

// Adds the prime factors of N to the given vector.
void factor(const mpz_class &N, std::vector<mpz_class> &factors)
{
std::queue<mpz_class> to_factor;
to_factor.push(N);

while (!to_factor.empty()) {
mpz_class n = to_factor.front();
to_factor.pop();
if (n == 1) {
continue; // Trivial factor.
} else if (mpz_probab_prime_p(n.get_mpz_t(), 5)) {
// n is a prime.
factors.push_back(n);
} else {
// n is a composite, so push its factors on the queue.
mpz_class d = getDivisor(n);
to_factor.push(d);
to_factor.push(n/d);
}
}
}

Это по сути прямой перевод псевдокод в Википедии, и полагается на GMP для больших чисел и для тестирования первичности. Реализация работает хорошо и может учитывать такие простые числа, как

1000036317378699858851366323 = 1000014599 * 1000003357 * 1000018361

но захлебнется, например,

1000000000002322140000000048599822299 = 1000000000002301019 * 1000000000000021121

Мой вопрос: могу ли я что-то сделать, чтобы улучшить это, кроме перехода на более сложный алгоритм факторизации, такой как Квадратичное сито?

Я знаю, что одним из улучшений могло бы быть сначала сделать несколько пробных делений по предварительно вычисленным простым числам, но это не помогло бы для продуктов нескольких больших простых чисел, таких как описанные выше.

Я заинтересован в любых советах по улучшению базового метода Ро Полларда, чтобы он мог обрабатывать большие композиции только из нескольких основных факторов. Конечно, если вы обнаружите какие-либо глупости в приведенном выше коде, я тоже заинтересован в них.

Для полного раскрытия: это домашнее задание, поэтому общие советы и указатели лучше, чем полностью закодированные решения. При таком очень простом подходе я уже получаю проходной балл по заданию, но, конечно, хотел бы улучшить его.

Заранее спасибо.