Простые числа без мистики: почему они бесконечны и зачем нужны компьютерам
Простые числа нельзя разложить на меньшие множители. Их бесконечно много, а большие простые помогают создавать ключи RSA.
Дальше вы пройдёте доказательство Евклида на конечном списке, поймёте проверку делителей до квадратного корня и увидите, какую именно задачу простые числа решают в RSA.
В статье вы узнаете:
Простое число нельзя собрать из меньших множителей
Натуральное число больше 1 называется простым, если у него ровно два положительных делителя: 1 и оно само. Числа 2, 3, 5, 7 и 11 простые. Число 12 составное, потому что делится на 2, 3, 4 и 6.
Единица не относится ни к простым, ни к составным. Если считать её простой, разложение на множители перестанет быть единственным: 6 можно будет записывать как 2 × 3, 1 × 2 × 3, 1 × 1 × 2 × 3 и бесконечно продолжать эту историю. Исключение единицы сохраняет удобное правило.
Основная теорема арифметики утверждает, что каждое целое число больше 1 раскладывается на простые множители единственным способом, если не учитывать их порядок.
Например, 756 = 2² × 3³ × 7. Можно начать деление с 2, с 3 или сразу заметить 7, но конечный набор простых множителей не изменится. Поэтому простые числа часто сравнивают с атомами целой арифметики: составные числа собираются из них умножением.
У сравнения есть граница. Простые числа не являются материальными частицами и не стоят в таблице готовым набором. Их бесконечно много, а промежутки между соседними простыми меняются.
Доказательство Евклида ломает любой конечный список
Предположим, что все простые числа удалось выписать: p1, p2, ..., pn. Перемножим весь список и прибавим единицу.
При делении N на любое простое из списка остаток равен 1. Значит, ни одно из них не делит новое число. При этом любое целое N > 1 либо само простое, либо имеет хотя бы один простой делитель. Этот делитель отсутствует в якобы полном списке. Получилось противоречие, поэтому конечного списка всех простых не существует.
В доказательстве есть ловушка. Число, полученное как произведение известных простых плюс один, не обязано быть простым. Для списка 2, 3, 5 и 7 получается 211, оно простое. Но для первых шести простых получаем 30 031 = 59 × 509. Доказательству достаточно, что у результата найдётся хотя бы один новый простой делитель.
Так Евклид не даёт удобную фабрику последовательных простых чисел. Он делает более сильную логическую работу: каким бы длинным ни был конечный список, за его пределами обязательно существует ещё один простой делитель.
Этот аргумент легко повторить на небольших значениях. Выпишите несколько первых простых, перемножьте их, прибавьте один и затем откройте калькулятор делителей числа. Если результат составной, среди его делителей всё равно появится простое число, которого не было в исходном списке.
Для точной проверки достаточно делителей до квадратного корня
Наивный способ проверяет деление числа n на все целые от 2 до n − 1. Большая часть работы лишняя. Если составное число записывается как n = a × b, хотя бы один множитель не превышает √n. Иначе оба были бы больше корня, а произведение превысило бы n.
Для числа 221 корень чуть меньше 15. Достаточно проверить простые делители 2, 3, 5, 7, 11 и 13. Последний подходит: 221 = 13 × 17. Проверять 17 отдельно уже не нужно, потому что парный меньший множитель найден.
Сначала можно отбросить чётные числа, затем кратные 3 и 5, после чего проверять только оставшихся кандидатов. Такой точный перебор хорошо работает для умеренных значений. Проверка простого числа на eCalc использует этот принцип для целых до 1012 и показывает делители, если число составное.
Для сотен и тысяч бит простого перебора уже недостаточно. Тогда программы используют быстрые тесты простоты. Часть тестов вероятностная: составное число может с очень малым шансом пройти один раунд, поэтому проверки повторяют с разными основаниями. Другие алгоритмы дают математически доказанный ответ, но могут требовать больше работы.
Найти делитель и доказать простоту являются разными задачами. Чтобы показать составность, достаточно одного нетривиального делителя. Чтобы доказать простоту простым перебором, нужно исключить всех подходящих кандидатов до квадратного корня.
Простые редеют, но не заканчиваются
В начале числовой прямой простые встречаются часто: среди чисел от 1 до 10 их четыре. Между 90 и 100 находится только 97. Дальше средняя доля простых уменьшается, хотя отдельные короткие промежутки ведут себя неровно.
Теорема о распределении простых говорит, что количество простых не больше x примерно равно x/ln x при больших x. Значит, рядом с x случайное целое имеет шанс порядка 1/ln x оказаться простым. Удвоение количества цифр не делает поиск невозможным: кандидатов становится больше, но проверять обычно приходится не астрономическую долю пространства.
Приближение описывает среднюю плотность, а не точное расписание. Иногда соседние простые отличаются на 2, как 101 и 103. Иногда появляется длинный промежуток составных чисел. Простые не распределены равномерно и не следуют короткому повторяющемуся узору.
Поэтому следующее простое обычно ищут практично: берут число, переходят к ближайшему нечётному кандидату и последовательно проверяют числа, пока тест не даст ответ. Это можно увидеть в поиске следующего простого числа: инструмент показывает не только результат, но и расстояние до него.
Программа не хранит бесконечный справочник простых. Она строит ответ из правил делимости и тестов. В этом смысле бесконечность не мешает вычислению: для каждой конкретной задачи нужен конечный участок.
RSA публикует произведение и прячет его множители
В RSA выбирают два больших простых числа p и q, затем перемножают их и получают модуль n = pq. Число n входит в открытый ключ. Сами множители сохраняют в секрете, потому что знание их разложения позволяет восстановить параметры закрытого ключа.
На игрушечном примере возьмём p = 61 и q = 53. Получается n = 3233. Разложить такое число легко даже вручную, поэтому пример ничего не защищает. Настоящие ключи используют числа с сотнями десятичных цифр и тщательно заданными процедурами генерации.
Шифрование и проверка подписи используют быстрое возведение в степень по модулю. Обратное действие становится доступным владельцу закрытого параметра. В исходной статье Рональд Ривест, Ади Шамир и Леонард Адлеман описали именно эту асимметрию: открытый способ преобразования не раскрывает практичный обратный путь без секретной информации. [Rivest, Shamir, Adleman, 1978]
Фраза «RSA держится на простых числах» слишком короткая. Простые удобны тем, что арифметика по модулю и количество взаимно простых остатков получают управляемую структуру. Практическая стойкость связана с трудностью разложения большого составного модуля и корректностью всей реализации, включая генератор случайных чисел, дополнение сообщений и защиту закрытого ключа.
Криптография использует больше одной математической трудности
Не вся защита данных сводится к факторизации. Симметричные шифры работают с битовыми преобразованиями и секретным ключом. Другие системы с открытым ключом опираются на дискретный логарифм в конечных группах, точки эллиптических кривых, решётки или иные задачи. Простые числа часто задают удобное конечное поле, но не играют везде одну роль.
Также нельзя взять любое большое простое, перемножить с соседом и получить безопасный RSA. Размеры, случайность, взаимная независимость множителей и правила формирования ключа имеют значение. Самодельная криптография опасна именно потому, что школьно понятная формула скрывает инженерные условия.
Простые числа остаются интересными без мистики. Их бесконечность следует из короткого доказательства, конкретное число проверяется конечным алгоритмом, а сложность обратного разложения помогает строить один из важнейших криптографических механизмов. Всё остальное начинается после точного вопроса: какое число проверяем, какой алгоритм используем и от какой атаки защищаемся.
Есть что добавить?
Напишите своё мнение, комментарий или предложение.