Простые числа

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

Простые числа — те числа, которые делятся без остатка только на само себя и 1. Это означает, что простое число нельзя представить в виде произведения (состоящего только из целых положительных чисел), кроме как:

[простое число] х 1 = [простое число]

Простые и составные

Составные числа — это натуральные числа больше 1, у которых есть делители помимо 1 и самого числа. Поэтому каждое натуральное число больше 1 либо простое, либо составное. Теорема о распределении простых чисел описывает их среднюю плотность: около большого числа n доля простых имеет порядок 1/ln(n). Значит, с ростом n простые встречаются в среднем реже.

Средний интервал между следующими друг за другом простыми числами к n приблизительно равен логарифму n, или ln(n).

Найти простое

Простейший тест простоты — проверять делимость n на целые числа от 2 до √n: если делителя на этом промежутке нет, составного множителя большего √n без парного меньшего множителя быть не может.

По состоянию на 2026 год крупнейшее известное простое число — 2^136279841 − 1. Оно содержит 41 024 320 десятичных цифр и было найдено Люком Дюрантом в проекте GIMPS в октябре 2024 года.

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

Решето Эратосфена

Евклид Александрийский, работавший примерно около 300 года до н. э., доказал, что простых чисел бесконечно много. Эратосфен (около 276–194 гг. до н. э.) описал метод, известный как решето Эратосфена, для систематического нахождения простых чисел до заданной границы.

Нарисуйте таблицу с 10 колонками и столькими рядами, сколько вам нужно, чтобы вместить числа, которые вы хотите проверить: если вы хотите проверить числа до n, нужно сделать таблицу от 1 до n. Начиная с 4, продвигайтесь по таблице и вычеркивайте все, что делится на 2. Затем вычеркните все, что делится на 3, затем — на 5, затем — на 7 и т. д., прокладывая путь сквозь простые числа. Вычёркивание достаточно продолжать по простым делителям не больше √n: все составные числа до n уже будут иметь хотя бы один такой делитель. Числа, которые не были зачеркнуты, — простые.

Прискорбное пренебрежение

После Древней Греции и вплоть до XVII в. в интерес к простым числам почти отсутствовал. Даже в XVII в., простые числа не использовались нигде, кроме как в чистой математике, но ими, по крайней мере, стало позволительно поиграть. Они заняли свое законное место в компьютерную эпоху, с появлением необходимости в разработке шифровальных алгоритмов.

Есть работа

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

Р₁ х Р₂ = С

Составное число используется для генерации кода, который называется открытый ключ, который банк (или кто-нибудь) посылает человеку, желающему зашифровать свои данные. Если вы покупаете что-нибудь онлайн, данные вашей кредитки должны быть зашифрованы с использованием этого публичного ключа, шифрование происходит на вашем конце связи. Зашифрованные данные окажутся пустым набор слов, если будут перехвачены в процессе передачи. Когда данные вашей карты прибывают на другой конец, закрытый ключ — созданный из Р₁ и Р₂ — используется для расшифровки.

В криптосистемах семейства RSA стойкость связана с вычислительной трудностью разложения очень больших составных чисел на простые множители. Нельзя корректно обещать фиксированное время вроде «1000 лет»: оно зависит от размера ключа, алгоритмов и вычислительных ресурсов. На практике современные защищённые соединения используют набор криптографических методов и параметры, которые со временем обновляются.