Ниже приведена моя реализация ро-алгоритма Полларда для простой факторизации:
#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
Мой вопрос: могу ли я что-нибудь сделать, чтобы улучшить это, за исключением переключения на более сложный алгоритм факторизации, такой как Квадратное решето?
Я знаю, что одно из улучшений могло бы состоять в том, чтобы сначала выполнить несколько пробных делений на предварительно вычисленные простые числа, но это не помогло бы для произведений нескольких больших простых чисел, таких как выше.
Меня интересуют любые советы по улучшению базового метода Ро Полларда, чтобы заставить его работать с более крупными композициями всего из нескольких простых множителей. Конечно, если вы найдете глупости в приведенном выше коде, они меня тоже заинтересуют.
Для полного раскрытия: это домашнее задание, поэтому общие советы и указатели лучше, чем полностью закодированные решения. Благодаря этому очень простому подходу я уже получаю проходной балл за задание, но, конечно, хотел бы улучшить его.
Заранее спасибо.
f(x)
изменит его поведение. Может быть, это поможет вам быстрее прогрессировать в больших простых числах? - person PureW   schedule 02.11.2013