Поллард Ро падает на входах, которые не слишком велики - PullRequest
Новая
       17

Поллард Ро падает на входах, которые не слишком велики

1 голос
/ 21 апреля 2019

Я реализовал алгоритм Полларда Ро, приведенный в Википедии 

x ← 2; y ← 2; d ← 1
while d = 1:
    x ← g(x)
    y ← g(g(y))
    d ← gcd(|x - y|, n)
if d = n: 
    return failure
else:
    return d

Большие входы дают ошибку:

GNU MP: Невозможно выделить память (размер = 4294950944)

Вот моя реализация 

mpz_class factor(mpz_class num)
{
    mpz_class x(2), y(2), d(1);
    while(d == 1)
    {
        x = polynomial(x);
        y = polynomial(polynomial(y));
        mpz_class diff = x - y;
        if(diff < 0)
        {
            diff *= -1;
        }
        mpz_gcd(d.get_mpz_t(), diff.get_mpz_t(), num.get_mpz_t());
    }
    if(d == num)
    {
        return -1;//failure
    }
    else
    {
        return d;//found factor
    }
}

mpz_class polynomial (mpz_class x)
{
    return ((x * x) + 1);
}

Она работает на входах типа 121, но вылетает на 5540987. Что-то не так?Есть ли способ, которым это можно улучшить, чтобы такие цифры можно было учесть?Я видел некоторые реализации , которые, по-видимому, используют полином ((x*x)%N+c)%N (обратите внимание на дополнительный мод n).Это работает, потому что можно использовать любой многочлен?

1 Ответ

1 голос
/ 21 апреля 2019

Имея две операции по модулю, есть избыточность, но одна из них решает именно эту проблему с числами, взрывающимися в размере, если алгоритм не завершается очень рано (что он делает для 121).

Это работает, потому что можно использовать любой многочлен?

Это немного более тонко, и бросание операций по модулю в микс на самом деле не случай "любого полинома". Ключ в том, что алгоритм ищет два значения в некоторой последовательности x[i] и x[j] с i != j, так что abs(x[i] - x[j]) кратно p (где N = pq и ни p, ни q равны 1), или, другими словами, abs(x[i] - x[j]) mod p = 0 или x[i] ≡ x[j] mod p. В этот момент цикл был найден в последовательности при просмотре по модулю p, и, что важно, если x[i] != x[j], тогда их разность ненулевое кратное p, что дает шанс извлечь коэффициент из N. По крайней мере, если их разность не кратна N (в этом случае результатом из GCD будет сам N, и коэффициент не будет получен).

Таким образом, если смотреть чисто на математику, то шаг по модулю N теоретически не нужен, а по циклу по модулю p происходит без такой «помощи». Но это возможно , N = pq, поэтому, если мы уменьшаем последовательность по модулю N, то ее свойства по модулю p не нарушаются и алгоритм все еще работает. Более того, уменьшение по модулю N очень важно практически, потому что оно предотвращает становление непрактично больших чисел, что в противном случае не только замедлит алгоритм, но и в конечном итоге приведет к сбою на реальном (конечном размере) оборудовании.

Это много теоретического обоснования, реализация очень проста, 

mpz_class polynomial (mpz_class x, mpz_class num)
{
    return ((x * x) + 1) % num;
}
...