Послание от внеземной цивилизации расшифровано! Вам, старшему IT-специалисту института SETI, поручили ознакомиться с ним и составить ответ. Похоже, что инопланетяне, вступившие в контакт, высокоразвиты, дружелюбны и бескорыстны, поэтому готовы поделиться своими достижениями с другими цивилизациями, которые уже достигли соответствующего уровня научно-технического прогресса. Решим поставленную перед нами задачу — докажем состоятельность человечества. От нас требуется найти простое число, состоящее из ста миллионов знаков. За это инопланетяне в подробностях поведают о своих наиболее важных достижениях. Благодаря им мы сумеем свести к нулю выбросы углекислого газа и, остановив таким образом глобальное потепление, спасем собственную планету. Сумеете ли вы обнаружить настолько монструозное число?

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

• с одним делителем;
• с двумя делителями;
• с тремя и более делителями.

Делитель — то, на что без остатка делится целое положительное число. Поскольку абсолютно любое число можно поделить на единицу, она является делителем для любого целого положительного числа. К примеру, 6 без остатка делится на 1, 2, 3 и 6: таким образом, у числа 6 четыре делителя, поэтому его можно спокойно поместить в третью категорию с составными числами (скоро вы поймете, почему они называются именно так). Первая категория мала: один-единственный делитель есть только у единицы. Вторая категория включает простые числа, которые делятся на нее и на себя. Вот несколько первых простых чисел: 2, 3, 5, 7, 11, 13, 17. Доказано, что существует бесконечное множество простых чисел. Они стоят особняком и могут здорово помочь вам при совершении покупок в интернете (этот момент мы разберем в подробностях чуть позже).

Существует удивительно элегантный математический факт — фундаментальная теорема арифметики. Ее суть полностью соответствует звучному наименованию. Во-первых, в теореме говорится: каждое целое положительное число, отличное от единицы, является либо простым, либо произведением простых чисел. Таким образом, составными называются числа, составленные из последовательно умноженных простых чисел. Во-вторых, теорема заявляет, что каждое составное число может быть представлено в виде произведения простых чисел одним-единственным способом. Например, 6 = 2 × 3. Или, скажем, 123 456 = 2 × 2 × 2 × 3 × 3 × 173. Каждый из приведенных примеров — уникальный, единственно возможный вариант представления составных чисел при разложении на простые множители. Поэтому мы вправе утверждать, что простые числа — своего рода ДНК всех прочих чисел.

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

Более 2000 лет назад Эратосфен, древнегреческий математик и глава легендарной Александрийской библиотеки, придумал алгоритм поиска простых чисел. Метод, ныне известный как «решето Эратосфена», включает в себя фильтрацию списка целых положительных чисел. Первое простое число — это 2. Отметив его как простое, вычеркиваете все остальные числа, кратные двум: они в любом случае будут составными. Переходите к следующему невычеркнутому числу — это будет 3. А затем избавляетесь от невычеркнутых чисел, кратных тройке. Возобновляете процесс: следующее число, которым вы еще не занимались, должно быть простым, в чем вы убедитесь, попытавшись разложить его на меньшие множители. Алгоритм хорош, но трудоемок. Если надо узнать, является ли 323 простым числом, придется делить его на меньшие простые числа, пытаясь установить его кратность 2 (нет), 3 (нет), 5 (нет), 7 (нет), 11 (нет), 13 (нет), 17 (да!). Поскольку 323 делится на 17, вы понимаете, что у него имеются как минимум три делителя (1, 17 и 323), и, следовательно, это число является не простым, а составным. Кстати, 323 = 17 × 19. Если составное число раскладывается только на действительно большие простые множители, то поиск таковых занимает много времени.

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

Простые числа играют большую роль в средствах криптографической защиты информации в интернете: взять, к примеру, алгоритм компании RSA Security, названной в честь ее основателей — по первым буквам их фамилий: Рональда Ривеста (Rivest), Ади Шамира (Shamir) и Леонарда Адлемана (Adleman). Это пример шифрования с открытым ключом: открытый ключ передается по открытому каналу и используется для шифрования сообщений, а расшифровка сообщений осуществляется при помощи закрытого ключа. Открытый ключ — это произведение двух больших простых чисел: суть в том, что сообщение легко шифруется, однако на его расшифровку без закрытого ключа могут уйти годы. Чем большие простые числа вы используете для создания публичного ключа, тем надежнее защищены ваши данные. Именно поэтому вы можете быть спокойны, делая покупки в интернете: на страже ваших банковских данных стоят простые числа.

А еще большие простые числа могут принести большие деньги. Фонд электронных рубежей (Electronic Frontier Foundation) — некоммерческая организация, выступающая за цифровую конфиденциальность, — предлагает премию в размере 150 000 долларов первому, кто найдет простое число, состоящее из 100 миллионов знаков. Так что вы можете не только спасти Землю, но и подзаработать! Однако для этого вам придется много делить, так что попробуйте повысить свои шансы дать миру новое простое число.

От половины чисел со 100 миллионами знаков можете сразу отмахнуться: ни одно четное число (кроме 2) не будет простым — ведь они по определению кратны 2. Спокойно избавляйтесь еще от одной десятой всех чисел — просто исключите все, которые заканчиваются пятеркой, поскольку они делятся на 5. Есть и другие ухищрения, но даже если вычеркнуть 90% чисел со 100 миллионами знаков, вас тем не менее ждет уйма работы с очень большими числами. Допустим, у вас есть самый мощный в мире компьютер, который проанализирует оставшиеся числа, — но все равно на поиск и проверку нужного числа уйдут долгие годы.

Что ж, прежде чем прибегнуть к грубой силе — простому перебору, давайте поищем: нет ли какой-нибудь уловки, способной помочь? В нашей ситуации пригодится идея Марена Мерсенна, французского священника XVII века. Мерсенн был чрезвычайно разносторонним человеком, у него есть музыкальные, философские и религиозные работы, но нас интересуют его труды, посвященные математике. Мерсенн писал о числах, представляющих собой разность между 2 в той или иной степени и 1. Эти числа известны как числа Мерсенна, а их формула выглядит так:

Mn = 2n – 1.

Чтобы найти первое число Мерсенна, принимаем n равным 1:

М1 = 21–1
= 2–1
= 1.

То же самое для n = 2:

М2 = 22–1
= 4–1
= 3.

Идея понятна. Вот первые одиннадцать чисел Мерсенна: 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047. Отлично! Но как эта формула поможет нам с простыми числами? Мерсенн обратил внимание, что если n — простое число, то и Mn, скорее всего, тоже будет простым:

В приведенном примере число 2047 представляет собой 23 × 89, что и делает его составным. Простые числа Мерсенна привлекли пристальное внимание научного сообщества, но, разумеется, без ошибок не обошлось — ведь электронные вычисления были еще невозможны. M67, которое, по мнению Мерсенна, являлось простым числом, оказалось составным: 267 – 1 соответствует 147 573 952 589 676 412 927, что, в свою очередь, равняется 193 707 721 × 761 838 257 287. Это было выявлено в 1903 году, спустя 250 лет после смерти Мерсенна.

Уже после Второй мировой войны, когда появились электронные калькуляторы, проверка простых чисел Мерсенна, которая и без того не прекращалась, набрала обороты. В 1952 году группа исследователей из Калифорнийского университета за несколько часов проверила два новых простых числа Мерсенна — M521 и M607. В общей сложности к текущему моменту обнаружено 51 простое число Мерсенна: они занимают семь верхних строчек в списке самых больших простых чисел, известных науке. Всякий раз, когда ученые находят новое простое число — по формуле Мерсенна или иным образом, — его можно использовать для проверки другого простого числа Мерсенна. Именно поэтому при помощи электронных вычислений по-прежнему ищут новые простые числа: раз от раза они становятся все больше и больше. На сегодня самое большое простое число Мерсенна — это M82589933, в котором почти 25 миллионов знаков.

Чтобы установить, в каком из чисел Мерсенна будет не меньше 100 миллионов знаков, воспользуемся известным нам математическим фактом: при возведении в степень основания 10 результат на один знак меньше, чем у показателя степени. Например:

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

2n – 1 ≥ 1099999999.

Это позволит нам пренебречь –1. Достаточно просто взглянуть на число из 100 миллионов знаков, как вычитание единицы тут же теряет всякий смысл. Теперь формула выглядит так:

2n > 1099999999.

Нужно найти n — в данном выражении это степень, — поэтому мы обращаемся к логарифмам (см. главу 13):

n > log2(1099999999).

Если вы попытаетесь вычислить значение n с помощью калькулятора, тот выдаст ошибку: 1099999999 — это слишком много для устройства. Но есть одно ухищрение. Возведение в степень — это результат многократного умножения числа на себя. К этой хитрости и прибегнем. 1099999999 — это 10, умноженное само на себя 99 999 999 раз. Будь у вас достаточно времени (и бумаги), вы могли бы записать нужное выражение таким образом:

1099999999 = 10 × 10 × 10 × … × 10.

Почему это важно? Потому что мы можем обратиться к основному свойству логарифмов: вне зависимости от основания log (a × a) = log (a) + log (a). Итак:

log2 (1099999999) = log2(10) + log2(10) + log2(10) +…+ log2(10).

Всего у вас 99 999 999 членов log2(10), то есть 99 999 999 × log2(10). Такое выражение калькулятору по силам:

n > 99 999 999 log2(10)
n > 332 192 806.

Получившееся число — 332 192 806 — сравнительно невелико и имеет всего девять знаков, так что вы можете начать поиск с любого уже проверенного простого числа, которое больше него. Экспресс-анализ сообщает, что в M31, обнаруженном Леонардом Эйлером в 1772 году (2 147 483 647), уже 10 цифр. Как знать, может, победителем станет M2147483647?

Последние семнадцать простых чисел Мерсенна были обнаружены благодаря проекту распределенных вычислений GIMPS (англ. — Great Internet Mersenne Prime Search). Участники проверяют простые числа Мерсенна с привлечением принадлежащего GIMPS программного обеспечения и собственной компьютерной техники любой доступной мощности. Такие хитрые ходы действительно помогают вам сузить поле поиска, однако оно все равно остается очень, очень широким.

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