Разложение на множители: проверить легко, разложить трудно

Если ты объяснишь, почему последовательность x² + c зацикливается по модулю неизвестного делителя за √p шагов, как из этого получить сам делитель и почему разложение всё равно остаётся трудной задачей, - листай до «Теперь сам».

Как думаешь, можно ли найти делитель, не перебирая

Число n = 99 999 640 000 243 составное - тест Миллера-Рабина сообщает об этом за пару сотен шагов. Оно равно произведению двух простых, каждое около десяти миллионов. Перебор делителей найдёт меньшее из них примерно за десять миллионов проб.

Прежде чем читать дальше, попробуй угадать: можно ли найти делитель за две с половиной тысячи проб, ничего не зная о нём заранее? И если можно - значит ли это, что разложение на множители перестало быть трудным?

На что это похоже

В группе из 23 человек у двоих, скорее всего, совпадает день рождения - хотя дней в году 365. Это парадокс дней рождения из раздела про хеширование: совпадение среди k случайных значений из m возможных становится вероятным уже при k около √m, потому что пар гораздо больше, чем значений.

Ро-метод ищет не делитель, а совпадение. Он порождает числа, которые выглядят случайными, и ждёт, когда два из них совпадут по модулю неизвестного простого p. Ждать приходится около √p шагов, а не p.

Механизм: цикл по модулю, которого мы не знаем

Пусть n = p · q. Строим последовательность: x заменяется на (x² + c) mod n. Числа прыгают по диапазону от 0 до n − 1 без видимого порядка.

Теперь посмотрим на те же числа по модулю p. Мы не знаем p, но остатки по нему существуют. Их всего p штук, и по парадоксу дней рождения примерно через √p шагов какой-то остаток повторится. А раз следующее число зависит только от текущего, после повтора последовательность по модулю p пошла по кругу.

n = 8633 = 89 · 97,   x → x² + 1,   начало x = 2

шаг            1     2     3      4      5      6
x mod 8633     5    26   677    781   5652   3005
x mod 97       5    26    95      5     26     95        ← по модулю 97 уже круг длиной 3

Числа на шагах 3 и 6 разные, но по модулю 97 оба дают 95. Значит их разность делится на 97: 3005 − 677 = 2328 = 24 · 97. С n у этой разности общий делитель 97 - и находит его алгоритм Евклида: НОД(2328, 8633) = 97. Делитель получен, хотя никто не делил n на 97.

Остаётся вопрос, какие два шага сравнивать: хранить все числа нельзя. Приём - черепаха и заяц: одна переменная делает один шаг за круг, вторая - два. Если последовательность вошла в цикл длины L, то в тот момент, когда номер круга делится на L, заяц обогнал черепаху на целое число оборотов и стоит на том же месте по модулю p. Сравнивать нужно только их, и на каждом круге - одним вызовом Евклида.

Название метода - от буквы ρ: хвост, по которому последовательность входит в круг, и сам круг.

Правило

Перебор делителей находит наименьший простой делитель p за p проб - не больше √n. Ро-метод Полларда находит какой-то делитель - чаще всего связанный с наименьшим простым p - в среднем за порядка √p кругов, не больше n^(1/4): на каждом круге черепаха делает один шаг x → x² + c, заяц два, и вычисляется НОД(|x − y|, n). НОД, отличный от 1 и от n, - делитель. Если НОД равен n, попытка не удалась, и её повторяют с другим c. Оба метода экспоненциальны по числу цифр. Перед разложением число проверяют на простоту: на простом числе ро-метод не остановится, пока цикл не замкнётся по самому n.

Разбор: перебор и числа, которые раскладываются легко

def razlozhi(n):
    out = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            out.append(d)
            n = n // d
        d = d + 1
    if n > 1:
        out.append(n)
    return out

Найденный делитель сразу выносится из n, и граница d * d <= n сжимается вместе с числом. razlozhi(360) возвращает [2, 2, 2, 3, 3, 5]. Число 254 803 968 = 2²⁰ · 3⁵ из девяти цифр раскладывается за 86 шагов: после двадцати пяти делений от него остаётся единица.

Трудность числа для перебора определяет не его размер, а его делители: цикл идёт до второго по величине простого множителя или до корня из наибольшего - смотря что больше. Число с мелкими множителями рассыпается мгновенно. Самый трудный случай - произведение двух простых одного размера: перебор идёт до корня.

Разбор: ро-метод против перебора

def ro(n, c):
    x = 2
    y = 2
    d = 1
    krugov = 0
    while d == 1:
        x = (pow(x, 2, n) + c) % n
        y = (pow(y, 2, n) + c) % n
        y = (pow(y, 2, n) + c) % n
        d = nod(abs(x - y), n)
        krugov = krugov + 1
    return [d, krugov]

x - черепаха, y - заяц, nod - алгоритм Евклида из прошлой главы, только без счётчика кругов: он возвращает одно число - сам НОД. Берём произведения двух соседних простых одного размера - самый трудный случай для перебора - и c = 1:

n                            меньший делитель    перебор, шагов    ро: кругов    ро: шагов
8 633                                 89                 266            3            117
99 400 891                         9 967              29 900           45          3 461
9 998 000 099                     99 989             299 966          525         50 153
999 962 000 357                  999 979           2 999 936          280         30 915
99 999 640 000 243             9 999 973          29 999 918        2 472        314 771
9 007 195 909 437 503         94 906 247               -            5 642        806 431

Ответ на первый вопрос из начала урока: да, 2472 круга вместо десяти миллионов проб. Делитель вырос в тысячу раз между второй и пятой строкой - кругов стало больше в пятьдесят пять раз, а по закону корня ожидалось около 32. Метод случайный, и разброс вокруг корня велик: четвёртая строка упала ниже ожидаемого, пятая поднялась выше. Но порядок держится: перебор платит за каждую цифру делителя вдесятеро, ро-метод - в среднем втрое. В первой строке метод нашёл больший из двух множителей, 97: по модулю 97 цикл замкнулся раньше, чем по модулю 89.

Ответ на второй вопрос: нет. Для ключа RSA в 2048 бит делитель - число из 1024 бит. Корень из него - 2⁵¹². Экспонента стала вдвое более пологой и осталась экспонентой.

Теперь неудача. Для n = 988 027 = 991 · 997 при c = 1 метод возвращает через 22 круга само n: цикл замкнулся по обоим делителям одновременно: заяц встал точно на черепаху, разность равна нулю, а nod(0, n) равен n. Это честный отказ, а не ошибка: с c = 2 находится 997 за 15 кругов.

Что ломается без этого

Первое: ро-метод на простом числе. Делителя нет, НОД остаётся единицей, пока заяц не догонит черепаху по самому n - около √n кругов. Сначала проверка простоты, потом разложение.

Второе: d == n принят за ответ. Программа сообщает, что n делится на n. Нужно сменить c и начать заново.

Третье: x * x вместо степени по модулю. При n больше 94 906 265 квадрат выходит за точность тренажёра, а в C - за 64 бита при n больше 2³².

Четвёртое: слишком близкие множители. Если p и q почти равны, n раскладывается как разность квадратов за несколько проб - этот приём придумал ещё Ферма. В 2022 году так вскрылись ключи, которые генерировала одна библиотека для принтеров: простые в них выбирались рядом друг с другом. Числа из таблицы выше - как раз такие: трудны они только для перебора и ро-метода.

Зачем это в работе

Стойкость RSA оценивают по лучшему известному алгоритму разложения - решету числового поля. Его цена растёт медленнее экспоненты, но быстрее любого многочлена. Публичные рекорды: в феврале 2020 года разложено число из 829 бит, а в сентябре 2026 года рекорд обновили дважды за шестнадцать дней - сначала 862 бита, потом 896 бит, 270 десятичных цифр. Второе разложение заняло около тридцати лет работы одной видеокарты, распределённых по двум тысячам карт. Поэтому ключи в 1024 бита считаются ненадёжными, а 2048 - нижней границей.

На квантовом компьютере задача меняет класс: алгоритм ШораРазбирается в разделе 21, глава «Квантовая модель - кубит, интерференция, алгоритм Шора»: Алгоритм Шора и границы: что квантовый компьютер ускоряет, а что нет раскладывает число за полиномиальное время. Числа, которые им разложили на настоящем железе, пока двузначные, но стандарты уже переводят на схемы, не зависящие от разложения. Об этом - следующая глава и раздел про границы вычислимого.

А ещё разложение нужно, чтобы посчитать функцию Эйлера. Для n = p · q она равна (p − 1)(q − 1), и без множителей её не узнать. Тот, кто знает множители, знает длину круга степеней по модулю n; тот, кто не знает, - нет. На этой разнице в знании устроен ключ RSA.

Теперь сам

1. Разложи 1001 перебором. Сколько делений понадобилось до первого найденного множителя?
2. В последовательности из механизма числа на шагах 2 и 4 равны 26 и 781, n = 8633. Что вычисляет ро-метод на втором круге и что у него получается?
3. Перебору на число из 20 цифр, произведение двух простых по 10 цифр, нужно около 10¹⁰ проб. Сколько кругов нужно ро-методу?
4. Ро-метод вернул d = n. Что случилось и что делать?