Ро-алгоритм Полларда

Наука умеет раскладывать целые числа на множители за $O(n^{\frac{1}{4}})$. Описываемый в этой статье алгоритм рандомизированный, поэтому нам сначала понадобится доказать одно утверждение из теории вероятностей.

Парадокс дней рождений

Пусть $f(n,d)$ это вероятность того, что в группе из $n$ человек ни у кого не совпали дни рождения. Будем считать, что дни рождения распределены независимо и равномерно в промежутке от $1$ до $d$.

$$f(n,d)=(1-\frac{1}{d})\times (1-\frac{2}{d})\times ...\times (1-\frac{n-1}{d})$$

Попытаемся оценить $f$:

$$\begin{array}{rlr}{e}^x& =1+x+\frac{x^2}{2!}+\dots & \text{(ряд Тейлора для экспоненты)}\\ & \simeq 1+x& \text{(аппроксимация для }|x|\ll 1\text{)}\\ e^{-\frac{n}{d}}& \simeq 1-\frac{n}{d}& \text{(подставим }\frac{n}{d}\ll 1\text{)}\\ f(n,d)& \simeq e^{-\frac{1}{d}}\times e^{-\frac{2}{d}}\times \dots \times e^{-\frac{n-1}{d}}& \\ & =e^{-\frac{n(n-1)}{2d}}& \\ & \simeq e^{-\frac{n^2}{2d}}& \end{array}$$

Из формулы более-менее понятно, что вероятность $\frac{1}{2}$ достигается при $n\approx \sqrt{d}$ и в этой точке изменяется быстро. Для самого алгоритма нам понадобится следующее:

Следствие. В мультимножество нужно добавить $O(\sqrt{n})$ случайных чисел от 1 до $n$, чтобы какие-то два совпали.

$\rho$-алгоритм Полларда

Итак, мы хотим факторизовать число $n$. Предположим, что $n=pq$ и $p\approx q$. Понятно, что труднее случая, наверное, нет. Алгоритм итеративно ищет наименьший делитель и таким образом сводит задачу к как минимум в два раза меньшей.

Возьмём произвольную «достаточно случайную» с точки зрения теории чисел функцию. Например $f(x)=(x+1{)}^2\mathrm{mod}n$.

Граф, в котором из каждой вершины есть единственное ребро $x\to f(x)$, называется функциональным. Если в нём нарисовать «траекторию» произвольного элемента — какой-то путь, превращающийся в цикл — то получится что-то похожее на букву $\rho$ (ро). Алгоритм из-за этого так и назван.

Рассмотрим траекторию какого-нибудь элемента $x_0$: {$x_0$, $f(x_0)$, $f(f(x_0))$, $\dots$}. Сделаем из неё новую последовательность, мысленно взяв каждый элемент по модулю $p$ — наименьшего из простых делителей $n$.

Утверждение. Ожидаемая длина цикла в этой последовательности $O(\sqrt[4]{n})$.

Доказательство: так как $p$ — меньший делитель, то $p\le \sqrt{n}$. Теперь просто подставлим в следствие из парадокса дней рождений: в множество нужно добавить $O(\sqrt{p})=O(\sqrt[4]{n})$ элементов, чтобы какие-то два совпали, а значит последовательность зациклилась.

Если мы найдём цикл в такой последовательности — то есть такие $i$ и $j$, что $f^i(x_0)\equiv f^j(x_0)(\mathrm{mod}p)$ — то мы сможем найти и какой-то делитель $n$, а именно $gcd(|f^i(x_0)-f^j(x_0)|,n)$ — это число меньше $n$ и делится на $p$.

Алгоритм по сути находит цикл в этой последовательности, используя для этого стандартный алгоритм («черепаха и заяц»): будем поддерживать два удаляющихся друг от друга указателя $i$ и $j$ ($i=2j$) и проверять, что $f^i(x_0)\equiv f^j(x_0)(\mathrm{mod}p)$, что эквивалентно проверке $gcd(|f^i(x_0)-f^j(x_0)|,n)\notin \{1,n\}$.

typedef long long ll;

inline ll f(ll x) { return (x+1)*(x+1); }

ll find_divisor(ll n, ll seed = 1) {
    ll x = seed, y = seed;
    ll divisor = 1;
    while (divisor == 1 || divisor == n) {
        // двигаем первый указатель на шаг
        y = f(y) % n;
        // а второй -- на два
        x = f(f(x) % n) % n;
        // пытаемся найти общий делитель
        divisor = __gcd(abs(x-y), n);
    }
    return divisor;
}

Так как алгоритм рандомизированный, при полной реализации нужно учитывать разные детали. Например, что иногда делитель не находится (нужно запускать несколько раз), или что при попытке факторизовать простое число он будет работать за $O(\sqrt{n})$ (нужно добавить отсечение по времени).

Примечания

Формально, мы показали, что алгоритм работает за $O(\sqrt[4]{n}\log n)$ за счёт поиска $gcd$, но сложной теорией чисел можно доказать, что этого логарифма в асимптотике на самом деле нет.

Факторизация больших чисел интересна в контексте криптографии — на предположение невозможности факторизации за линейное время опирается, например, алгоритм RSA.

Существуют также субэкспоненциальные, но не полиномиальные алгоритмы факторизации. Человечество умеет факторизовывать числа порядка $2^{200}$.

Алгоритм Шора позволяет факторизовывать числа за полиномиальное время на квантовом компьютере. Но на 2019 год все квантовые вычисления проще симулировать на обычном компьютере. Самое большое число, факторизованное на реальном квантовом компьютере — 4088459.