Вызов простоты: что такое простые числа и почему на самом деле с ними всё очень сложно

Самые простые вопросы — самые сложные. Иначе почему математики столетиями бьются над загадками чисел, которые проходят в пятом классе? Рассказываем, почему название «простые числа» обманчиво и как решение абстрактной математической задачи угрожает не только вашему кошельку, но и всей мировой экономике

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

Непростые простые числа

Знакомство с математикой начинается с умения считать. Натуральные числа — 1, 2, 3 и так далее — самые естественные и незамысловатые математические объекты, какие только можно вообразить. Более хитрые понятия — дроби, функции и т. д. — строятся на их основе: как сказал выдающийся математик Леопольд Кронекер, «Бог создал целые числа, все остальное — дело рук человеческих». А ведь натуральные числа еще проще целых — они всегда положительные.

В этом смысле натуральные числа — первоэлементы, кирпичики, из которых состоит бóльшая часть математики (не вся, так как некоторые области математики вообще не имеют дела с числами. — Прим. ред.). Но и среди натуральных чисел есть собственные неделимые «кирпичики», из которых состоят остальные числа.

Рассмотрим для примера несколько вот таких чисел: 4 = 2 × 2; 6 = 2 × 3; 7843 = 11 × 23 × 31. Все эти числа относятся к составным. Смысл этого слова прозрачен: например, число 6 составлено из чисел 2 и 3 с помощью умножения. А из чего составлено само число 2? Ни из чего, кроме самого себя: 2 = 2 × 1, и все (напомним, что мы здесь говорим о натуральных числах, а не о дробях, поэтому нас сейчас не интересуют выражения, подобные таким: 2 = 1/2 × 4). И дело не в том, что число 2 такое маленькое. Число 9929 тоже простое — так называются числа, начиная с 2, которые делятся только на единицу и на себя. Таким образом, первые 10 простых чисел выглядят так: 2, 3, 5, 7, 11, 13, 17, 19, 21, 23. А вот число 1 не считается простым!

Зачем нужны такие числа?

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

Самый очевидный способ зашифровать сообщение — придумать секретное обозначение для каждой буквы. Например, буква А будет обозначаться числом 2, Б — числом 9, О — числом 7. Тогда 927929 будет означать «баобаб». Только не теряйте памятку, какая буква как обозначена! Этот листок нужен и чтобы зашифровать сообщение («замок»), и чтобы расшифровать его («ключ»).

В том, что замок и ключ — одно и то же, и состоит проблема. Допустим, вы онлайн переводите деньги со счета на счет. Чтобы вы могли зашифровать свое сообщение банку, банк присылает вам свой фирменный замок. Но что будет, если его перехватит злоумышленник? Раз замок одновременно и ключ, хакер сможет «открыть» этим ключом данные и украсть ваши деньги.

Гораздо лучше, когда замок и ключ — разные вещи. Банк выдает клиентам замки, ключи от которых есть только у него. Даже если хакер перехватит замок, он не сможет им ничего открыть, только закрыть! Другими словами, банк должен сообщить вашему смартфону способ зашифровать сообщение так, чтобы никто, кроме банка — даже вы сами, — не мог его расшифровать.

Первый такой шифр придумали Рональд Ривест, Ади Шамир и Леонард Адлеман в 1970–х. По первым буквам их фамилий этот способ шифрования назвали RSA. «Ключ» в этой системе — два больших простых числа, а «замок» — их произведение. Как именно с их помощью шифруют сообщения — это технические детали, которые мы опустим. Важно, что банк сообщает вам только произведение, а сами простые множители держит в секрете.

Фокус в том, что перемножить два простых числа легко, а вот найти множители по их произведению гораздо труднее. Из каких простых чисел стоит число 87404987? Надо проверить, делится ли оно на 2, 3, 5, 7, 11… Придется перебрать немало чисел, чтобы установить, что 87404987 = 8803 × 9929. А ведь в этом числе всего 8 цифр.

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

Проверка на простоту

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

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

Применяемые на практике тесты на простоту столь же быстрые, как «проверка кольца», но гораздо более надежные. Правда, они тоже не дают абсолютно точного ответа, простое данное число или составное. Но вероятность ошибки так мала, что ею можно пренебречь. Как говорится, скорее уж кирпич упадет на голову.

Есть ли самое большое простое число?

Убедившись в полезности простых чисел, оставим в покое криптографию и вернемся к числам как таковым. Зададимся для начала самым естественным вопросом: сколько всего простых чисел? Этот вопрос возник неспроста.

Простые числа встречаются чем дальше, тем реже. В первой сотне натуральных чисел 25 простых (25% чисел), в первой тысяче 168 простых (менее 17%), а в первом миллионе — 78 498 (менее 8%). Если подумать, это неудивительно. Числу 107 легко оказаться простым: нужно только не делиться ни на одно из простых чисел, меньших √107≈ 10, а их всего четыре (2, 3, 5, 7). Дальше можно не проверять, ведь произведение любых других простых чисел точно превысит 107: уже даже 11 × 11 = 121. А вот числу 1007 оказаться простым было бы труднее: ему пришлось бы не делиться ни на одно из простых чисел, меньших √1007 ≈ 32. И так уж вышло, что 1007 = 19 × 53.

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

Максимальное простое число

Самое большое простое число, известное сегодня, — это 2^136279841 — 1. В нем — вдумайтесь! — более 41 миллиона цифр. Но не подумайте, будто есть полный список простых чисел от 2 до 2^136279841 — 1. Это совсем не так. Дело в том, что числа вида 2^p — 1, где p — простое число (они называются числами Мерсенна), легко поддаются проверке на простоту. Поэтому самые большие известные простые числа — числа Мерсенна. Они одиноко возвышаются над неисследованным числовым океаном.

А что все-таки насчет полного списка? Хорошая программа на обычном ноутбуке находит все простые числа до триллиона (12 цифр) меньше чем за минуту. До какого же предела нам известны все простые числа? Другими словами, о каком минимальном числе мы еще не знаем, простое оно или составное? Где проходит граница неизведанного?

Похоже, что все простые числа длиной примерно до 20 цифр уже неоднократно вычислялись. Точнее сказать трудно: как ни удивительно, но точный ответ на этот вопрос не интересен ни ученым, ни IT-специалистам. Для шифровальщиков опасно «подходить к краю»: мощность компьютеров растет слишком быстро, сегодняшний передний край завтра станет глубоким тылом. Поэтому они берут колоссальные числа, заведомо слишком большие для взлома. Математики же интересуются свойствами, которые выполняются для всех простых чисел сразу, велики они или малы. Так что и им такой список ничего не даст.

Как далеко до соседа?

Мы упомянули, что простые числа встречаются чем дальше, тем реже. Но это если считать их общее количество в первой десятке, сотне, тысяче и т. д. А вот с расстояниями между соседними простыми числами все гораздо хитрее. Допустим, мы наткнулись на простое число. Как далеко от него следующее простое? Ответ удивителен: «Никогда заранее не скажешь». Бывает, что соседние простые числа различаются лишь на двойку: 3 и 5, 5 и 7, 11 и 13 и т. д. Такие простые числа называются близнецами. Но иногда соседние простые числа очень далеки друг от друга.

Можно ли указать хотя бы максимальный «срок ожидания» следующего простого? Можно, но для каждого числа он будет свой. Математик Пафнутий Чебышев доказал, что для простого числа N «срок ожидания» следующего простого не больше N+2. Например, число 7 — простое. Теорема Чебышева говорит, что среди следующих девяти чисел, от 8 до 16, обязательно будет хотя бы одно простое (на самом деле их даже два, это 11 и 13).

Однако доказано, что найдутся соседние простые, разделенные хоть миллионом составных чисел, хоть миллиардом, хоть вообще любым умопомрачительным количеством, которое вы выберете. Правда, и сами «соседи» окажутся большими. Например, первые 17 составных чисел подряд находятся между простыми числами 523 и 541.

Чего мы не знаем о простых числах

Математики изучают простые числа не первое тысячелетие. Тем удивительнее огромное количество связанных с ними загадок. Мы упомянем только некоторые из них. Возьмем, например, уже знакомые нам числа-близнецы (напомним, что это простые числа, которые отличаются на два, вроде 3 и 5). Есть ли самая большая пара близнецов или всегда найдется пара еще больше? Никто не знает. Простые «числа-кузены» отличаются на четверку: 3 и 7, 7 и 11, 13 и 17 и т. д. Есть ли самая большая пара «кузенов»? И этого тоже никто не знает.

Возможно, самая знаменитая гипотеза о простых числах — гипотеза Гольдбаха. Этот немецкий математик предположил, что любое четное число больше 2 можно представить в виде суммы двух простых чисел. Так, 4 = 2 + 2, а, например, 16 = 13 + 3. Это правило выглядит очень красиво и выполняется для всех четных чисел, какие только смогли проверить компьютеры. Соблазнительно думать, что оно выполняется всегда.

Но что если существует невообразимо огромное число, которое опровергает гипотезу Гольдбаха? Пусть оно слишком велико, чтобы досчитать до него с единицы, но, быть может, его получится определить каким-то обходным путем. Тогда гипотеза Гольдбаха будет опровергнута, и с некоторыми красивыми математическими гипотезами это уже случилось. А может быть, кто-то докажет гипотезу Гольдбаха, превратив ее в теорему. Это будет достижение того же уровня, что и доказательство теоремы Ферма.

_{Иллюстрации: Виктор Богорад}

_{Материал опубликован в марте 2025}