Простые числа и тесты простоты
Асимметричной криптографии нужны простые числа из сотен и тысяч бит. Как найти такое число и убедиться, что оно действительно простое, если разложить его на множители невозможно? В статье — от пробного деления до вероятностных тестов и строгого доказательства простоты по критерию Поклингтона, которое использует лаборатория.
Сколько вокруг простых чисел
Количество простых чисел, не превосходящих N, приблизительно равно
Значит, случайное число около N простое с вероятностью примерно 1/ln N. Для 1024-битных чисел ln 2^1024 ≈ 710: в среднем каждое 710-е число простое, а среди нечётных — каждое 355-е. Простых чисел нужного размера очень много, и случайный поиск быстро натыкается на них — нужен только быстрый способ проверки.
Пробное деление
Если у n есть делитель, то есть и делитель не больше √n. Поэтому достаточно проверить делимость на 2, 3, …, ⌊√n⌋. Это строгий метод, но для 1024-битного числа пришлось бы проверить около 2^512 делителей — больше, чем атомов во Вселенной. В лаборатории пробное деление используется для p до 10^9 и для самого первого звена цепочки Поклингтона.
Тест Ферма
По малой теореме Ферма, если n простое и n ∤ a, то
Значит, если для какого-то a сравнение не выполнено, n точно составное — даже не зная ни одного его делителя. Проверка требует одного возведения в степень, то есть O(log n) умножений.
Обратное неверно. Существуют составные числа, для которых a^(n−1) ≡ 1 (mod n) при всех a, взаимно простых с n. Наименьшее — 561 = 3·11·17: например, 2^560 ≡ 1 (mod 561). Таких чисел бесконечно много (Алфорд, Гранвиль, Померанс, 1994), поэтому тест Ферма сам по себе ненадёжен.
Тест Миллера–Рабина
Запишем n − 1 = 2^s·d, где d нечётно. Для простого n у сравнения x² ≡ 1 есть только корни ±1, поэтому последовательность a^d, a^(2d), …, a^(2^s·d) либо начинается с 1, либо содержит −1. Если это не так, a — свидетель того, что n составное.
Для составного нечётного n не больше четверти оснований a не являются свидетелями.
После m раундов со случайными основаниями составное число пропускается с вероятностью не больше 4^(−m); при 40 раундах это 2^(−80). Миллер–Рабин — стандарт де-факто в криптографических библиотеках. Однако его ответ «простое» — это лишь «простое с очень высокой вероятностью», а не доказательство. Для строгого доказательства есть детерминированные алгоритмы: тест AKS (2002) работает за полиномиальное время, но медленно на практике; метод эллиптических кривых (ECPP) быстр, но сложен. Если число строится специальным образом, доказательство даёт простой критерий Поклингтона.
Критерий Поклингтона
Пусть n − 1 = F·R, где разложение F на простые множители известно и F > √n. Если для каждого простого q | F найдётся основание a, такое что
то n простое.
Доказательство. Пусть r — любой простой делитель n, q^e — максимальная степень q, делящая F.
- Из a^(n−1) ≡ 1 (mod r) следует, что порядок a по модулю r делит n − 1.
- Из НОД(a^((n−1)/q) − 1, n) = 1 следует a^((n−1)/q) ≢ 1 (mod r): порядок не делит (n − 1)/q.
- Значит, порядок делится на q^e. Порядок делит r − 1 (теорема Ферма), поэтому q^e | r − 1.
- Это верно для всех q | F, следовательно F | r − 1 и r > F > √n.
У составного n есть простой делитель, не превосходящий √n, — противоречие. Значит, n простое.
- q = 29 — простое (пробное деление).
- n = 2·29 + 1 = 59: F = 29 > √59 ≈ 7,7. Основание a = 2: 2^58 ≡ 1 (mod 59) и НОД(2^2 − 1, 59) = НОД(3, 59) = 1. Значит, 59 простое.
- n = 12·59 + 1 = 709: F = 59 > √709 ≈ 26,6. При a = 2: 2^708 ≡ 1 (mod 709) и НОД(2^12 − 1, 709) = НОД(4095, 709) = 1. Значит, 709 простое.
Каждое звено опирается на предыдущее: доказанное простое q становится множителем F для следующего, вдвое более длинного числа.
Генерация простых с доказательством
На этой идее основан алгоритм генерации, который используется в лаборатории (близкий к методу Маурера, 1995). Чтобы получить простое из b бит:
- Если b мало (до 24 бит), взять случайное число и проверить пробным делением.
- Иначе рекурсивно получить доказанное простое q примерно из b/2 + 2 бит — так что q² > n.
- Составить чётное R из случайных малых простых так, чтобы n = R·q + 1 имело ровно b бит.
- Отсеять n с малыми делителями, затем перебрать основания a = 2, 3, …: если a^(n−1) ≢ 1 — n составное, взять новое R; если выполнено и НОД(a^R − 1, n) = 1 — n доказано простым.
Результат — сертификат простоты: цепочка чисел с основаниями a, которую любой может перепроверить за доли секунды, не повторяя поиск. Сервер лаборатории так и делает: сертификат отправляется в браузер вместе с ключами и перепроверяется при каждом шифровании. Бонус построения — полностью известное разложение p − 1 = R·q: оно необходимо, чтобы проверить, что g — первообразный корень.
Для 1024 бит цепочка выглядит так: 19 → 35 → 67 → 131 → 259 → 514 → 1024 бит, всего 7 звеньев. На каждом звене перебирается порядка сотни кандидатов — генерация занимает доли секунды.
Простые получаются особого вида: p − 1 всегда равно «большое простое × произведение малых простых». Для учебных целей и для протокола Эль-Гамаля это допустимо, но такие числа не распределены равномерно среди всех простых нужной длины.
В разделе «Шифр Эль-Гамаля» задайте размер p в битах и нажмите «Большое простое (Поклингтон)». После передачи сообщения в разборе появится таблица сертификата: каждое звено цепочки, q, разложение R, основание a и число перебранных кандидатов. Открыть →
Вопросы для самопроверки
- Докажите, что 341 составное, с помощью теста Ферма с основанием 3.
Ответ
3^340 mod 341 = 56 ≠ 1, значит 341 составное (341 = 11·31). Заметьте: с основанием 2 тест не сработал бы — 2^340 ≡ 1 (mod 341). - Почему в критерии Поклингтона нужно условие F > √n?
Ответ
Из условий следует лишь, что каждый простой делитель r больше F. Чтобы исключить составное n, нужно, чтобы F было не меньше √n: у составного числа есть делитель ≤ √n. - Сколько в среднем нечётных 512-битных чисел нужно проверить, чтобы найти простое?
Ответ
Около ln(2^512)/2 ≈ 355/2 ≈ 177.