Если число в виде string, то можно столбиком:
1 2018-03-25 23:48:40
Re: Длинная арифметика.Умножение длинного на короткое (5 ответов, оставленных в Algo)
2 2018-03-25 23:38:08
Re: Эффективные алгоритмы факторизации: under investigation (4 ответов, оставленных в Algo)
Алгоритм очень простой, но есть нюансы в начальных значениях. Я считаю, что наиболее адекватно он представлен в демофайле пакета 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);
}
4 2018-03-25 23:24:47
Re: Теория чисел. Факторизация. Проверка на простоту (3 ответов, оставленных в Algo)
Забудь про методы типа Поларда и обрати внимание на модификации метода Ферма, например Диксона или Померанца.