Тема: Эффективные алгоритмы факторизации: under investigation
После последнего Петрозаводска у меня закрались сомнения, не палево ли у меня там написано, особенно в алгоритмах Полларда 
Кто-нибудь может авторитетно заявить, что да, полное палево? 
Re: Эффективные алгоритмы факторизации: under investigation
С ним есть определенные непонятки -
пытался его сдать в
https://www.spoj.pl/problems/FACT0/
решает на long long в 2.13
хотя простенький python
def pollard_rho(n, iterations_count):
b0 = random.randint(0, n - 1)
b1 = b0
b1 = mulmod(b1, b1, n)
b1 += 1
if (b1 == n):
b1 = 0
g = gcd(abs(b1 - b0), n)
count = 0
while (count < iterations_count and (g == 1 or g == n)):
count += 1
b0 = mulmod (b0, b0, n)
b0 += 1
if (b0 == n):
b0 = 0
b1 = mulmod (b1, b1, n);
b1 += 1
b1 = mulmod (b1, b1, n);
b1 += 1
if (b1 == n):
b1 = 0
g = gcd (abs (b1 - b0), n)
return g
справился за 1.05
Re: Эффективные алгоритмы факторизации: under investigation
А ты, кстати, что запускал? Одну функцию, которая всю работу делает сама? Она, может быть, плохие константы использует для тупого алгоритма trial-division, и из-за него может быть тормоза?
Re: Эффективные алгоритмы факторизации: under investigation
Посмотрел внимательнее - оказалось такое время получилось когда я свой BigInteger прицепил к темплейтам. На long long сдавалась за 0.29.
Так что вроде все не так и плохо.
Re: Эффективные алгоритмы факторизации: under investigation
Алгоритм очень простой, но есть нюансы в начальных значениях. Я считаю, что наиболее адекватно он представлен в демофайле пакета GMP (папка demos, файл factorize.c). Там правда написано все в стандарте обычного С, но можно легко переделать под С++.
void factor_using_pollard_rho (mpz_t n, unsigned long a, struct factors *factors)
{
mpz_t x, z, y, P;
mpz_t t, t2;
unsigned long long k, l, i;
if (flag_verbose > 0)
{
printf ("[pollard-rho (%lu)] ", a);
}
mpz_inits (t, t2, NULL);
mpz_init_set_si (y, 2);
mpz_init_set_si (x, 2);
mpz_init_set_si (z, 2);
mpz_init_set_ui (P, 1);
k = 1;
l = 1;
while (mpz_cmp_ui (n, 1) != 0)
{
for (;;)
{
do
{
mpz_mul (t, x, x);
mpz_mod (x, t, n);
mpz_add_ui (x, x, a);
mpz_sub (t, z, x);
mpz_mul (t2, P, t);
mpz_mod (P, t2, n);
if (k % 32 == 1)
{
mpz_gcd (t, P, n);
if (mpz_cmp_ui (t, 1) != 0)
goto factor_found;
mpz_set (y, x);
}
}
while (--k != 0);
mpz_set (z, x);
k = l;
l = 2 * l;
for (i = 0; i < k; i++)
{
mpz_mul (t, x, x);
mpz_mod (x, t, n);
mpz_add_ui (x, x, a);
}
mpz_set (y, x);
}
factor_found:
do
{
mpz_mul (t, y, y);
mpz_mod (y, t, n);
mpz_add_ui (y, y, a);
mpz_sub (t, z, y);
mpz_gcd (t, t, n);
}
while (mpz_cmp_ui (t, 1) == 0);
mpz_divexact (n, n, t); /* divide by t, before t is overwritten */
if (!mp_prime_p (t))
{
if (flag_verbose > 0)
{
printf ("[composite factor--restarting pollard-rho] ");
}
factor_using_pollard_rho (t, a + 1, factors);
}
else
{
factor_insert (factors, t);
}
if (mp_prime_p (n))
{
factor_insert (factors, n);
break;
}
mpz_mod (x, x, n);
mpz_mod (z, z, n);
mpz_mod (y, y, n);
}
mpz_clears (P, t2, t, z, x, y, NULL);
}