Почему именно простые числа защищают ваши пароли

Число, которое нельзя разложить ни на что, кроме единицы и самого себя, — оказывается самым надёжным охранником в цифровом мире.

Сила простых чисел не в том, что они редкие, а в том, что их произведение почти невозможно «расцепить» обратно.

Простое число — это целое число больше единицы, которое делится без остатка только на $1$ и на себя: $2, 3, 5, 7, 11, 13, \dots$ Школьная скукота? А вот и нет: на этом скромном определении держится защита миллиардов транзакций ежедневно.

Атомы арифметики

Основная теорема арифметики гласит: любое целое число раскладывается на простые множители единственным способом. Например, $60 = 2^2 \cdot 3 \cdot 5$ — и других вариантов нет. Простые числа — это «атомы», из которых собраны все остальные числа, неделимые кирпичики мироздания чисел.

Эта единственность разложения и есть тот рычаг, которым пользуется криптография.

Лёгкий путь туда и адская дорога обратно

Возьмём два больших простых числа и перемножим — получим огромное составное число. Операция мгновенная даже для калькулятора. А теперь задача наоборот: дано большое число, найдите его простые множители. И тут всё ломается.

Для числа из 600 цифр не существует алгоритма, который справился бы за разумное время. Перебирать делители? Их астрономически много. Именно эта пропасть между «перемножить» и «разложить» прячет ваш пароль за непробиваемой стеной.

Почему перебор не помогает

Если число имеет $300$ десятичных цифр, количество кандидатов в делители превышает число атомов в наблюдаемой Вселенной. Даже проверяя триллион вариантов в секунду, вы не закончите за время существования Солнца. Математика здесь играет на стороне защитника.

Их бесконечно много — и это важно

Ещё Евклид доказал: простых чисел бесконечно много. Доказательство красивое: предположим, что их конечный список $p_1, p_2, \dots, p_k$. Перемножим все и прибавим единицу:

$$N = p_1 \cdot p_2 \cdot \ldots \cdot p_k + 1$$

Это $N$ не делится ни на одно простое из списка (всегда остаётся остаток $1$), значит, либо $N$ само простое, либо имеет простой делитель вне списка. Противоречие! Список не может быть полным.

Для криптографии бесконечность критична: всегда найдутся свежие, никем не использованные простые числа для новых ключей.

Как находят гигантские простые

Компьютер не перебирает все числа подряд. Он берёт случайное огромное число и быстро проверяет тестом на простоту — например, вероятностным тестом Миллера—Рабина. Тест не раскладывает число, а лишь отвечает «скорее всего простое» или «точно составное», и делает это молниеносно.

От простого числа к ключу

Как именно простые охраняют пароль? Когда вы заходите на защищённый сайт, ваш браузер и сервер договариваются о ключе шифрования, опираясь на пару огромных простых чисел. Подслушивающий видит только их произведение и обрывки переписки — а чтобы добыть сам ключ, ему пришлось бы разложить это произведение на множители. То есть совершить вычислительно невозможное. Простые числа не прячут ваш пароль буквально, а строят вокруг него математическую стену, которую нечем пробить.

Тонкая грань

Вся защита держится на предположении, что быстрого алгоритма факторизации не существует. Никто этого строго не доказал — просто за десятилетия его не нашли. Если завтра кто-то изобретёт такой алгоритм (или достроит квантовый компьютер), привычной криптографии придёт конец. Поэтому простые числа — это не просто математика, а живая линия фронта, на которой решается судьба вашей приватности.