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

833
8

Числа бывают разные: вещественные и мнимые, целые и рациональные, составные и, конечно, простые. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — продолжите этот ряд сами: простыми называются числа, которые делятся нацело только на себя и на единицу.

«Сама единица не относится ни к простым, ни к составным числам», — пояснил нам старший научный сотрудник Отдела алгебры и теории чисел Математического института имени Стеклова РАН Максим Королев.

Детали чисел

Простые числа — это как бы «кирпичики», из которых сложено все здание натуральных чисел. Основная теорема арифметики утверждает, что каждое натуральное число может быть представлено в виде произведения простых, и притом единственным способом например, 6 = 2 * 3, 15 = 3 * 5, 84 = 2*2*3*7. Простые числа являются элементарными деталями, «атомами», из которых составляются «молекулы» всех положительных целых чисел.

Интерес к простым числам проявляли еще математики Древней Греции. Они были знакомы с некоторыми свойствами простых чисел, располагали алгоритмом их поиска и, безусловно, видели их математическую красоту.

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

«Позднее математики — например, Джон Литтлвуд — утвердительно отвечали на вопрос о том, может ли работа в две строчки быть признана диссертационной. Без сомнения, к их числу относится и доказательство Евклида — добавляет Максим Королев. — Смотрите: допустим, имеется только конечное число простых: 2, 3, 5, 7 и так далее — и до самого последнего N, больше которого простых уже нет. Перемножим все эти простые числа, и прибавим к их произведению единицу. Получится новое число, которое не делится нацело ни на одно из исходного набора простых чисел. Но наименьший делитель этого числа, отличный от единицы, обязан быть простым, отличным от всех перечисленных. Получается противоречие».

СБПЧ

Простыми числами продолжали заниматься и европейские математики позднего Возрождения и нового времени — у всех на слуху такие имена, как Пьер Ферма, Рене Декарт, Блез Паскаль, Леонард Эйлер. Менее известен друг Ферма, францисканский священник Марен Мерсенн, который обратил внимание на числа особого вида — степени двойки, уменьшенные на единицу: 21 — 1 = 1, 22 — 1 = 3, 23 — 1 = 7, 24 — 1 = 15,… Мерсенн заинтересовался распределением простых и составных чисел в этой последовательности, и с тех пор простые числа такого вида носят названия простых чисел Мерсенна. Существуют достаточно быстрые математические алгоритмы проверки таких чисел на простоту. Поэтому самое большое простое число из известных на сегодняшний день является именно числом Мерсенна. Это число, равное 257885161 — 1, было обнаружено в январе 2013 года. К сожалению, привести его здесь целиком нет никакой возможности, поскольку его запись содержит больше 17 миллионов цифр.

«Хотя самое большое из найденных простых Мерсенна невообразимо велико, — поясняет Максим Королев, — всего в этом ряду известно только 48 простых чисел. Более того, оно может оказаться и последним: конечно ли количество простых чисел Мерсенна, или нет — это еще нерешенная проблема. Встречаются они очень редко, и пока неясно даже, существует ли какая-то зависимость между номером простого числа Мерсенна и его величиной. Это трудная задача; если такая закономерность будет найдена, она заметно ускорит поиск новых больших простых чисел».

Другая открытая проблема связана с так называемыми простыми числами Ферма. Так называются простые числа в последовательности, образованной по следующему правилу: к единице прибавляется двойка, возведенная в степень, которая сама является степенью двойки. Первые члены этой последовательности легко подсчитать: 21 + 1 = 3, 22 + 1 = 5, 24 + 1 = 17, 28 + 1 = 257, 216 + 1 = 65537. Все они оказываются простыми числами. Сам Ферма, проведя эти подсчеты, предположил, что эта закономерность сохранится и далее.

Однако уже Эйлер показал, что уже следующее число Ферма, 232+1, будет составным и делится на 641. С тех пор, несмотря на все усилия суперкомпьютеров, не обнаружено ни одного нового простого числа Ферма. Возможно, их вовсе нет. Но доказать этот факт еще никому не удалось.

И в числах Мерсенна, и в числах Ферма двойка появляется неспроста. Это единственное четное простое число, и при возведении в степень и прибавлении (или отнятии) единицы оно даст число нечетное, которое хотя бы потенциально может оказаться простым. В отличие от двойки, другие простые числа нечетные, и при тех же операциях они превратятся в четные числа, которые простыми быть уже не могут. Помимо себя и единицы, они обязательно будут делиться на два.

Корень шифрования

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

Чтобы понять, что это такое, возьмем для начала семерку. При делении на нее любые числа могут давать в остатке, помимо нуля, 1, 2, 3, 4, 5 или 6. Говорят, что эти числа образуют полную систему вычетов (остатков) по модулю 7. С этими остатками связана довольно забавная арифметика, непохожая на ту, что знакома большинству из нас со школы.

Возьмем любые два вычета — скажем, 4 и 5 — и сложим их: 4 + 5 = 9. Поделив результат на 7, в остатке получим 2. Двойку объявим суммой вычетов 4 и 5. В этом случае принято говорить, что сумма 4 и 5 сравнима с 2 по модулю 7.

Аналогично, суммой вычетов 6 и 2 объявим не 8 = 6+2, а остаток от деления восьмерки на 7. Таким образом, сумма 6 и 2 сравнима с единицей по модулю 7. Подобным образом вычеты можно и перемножать.

Теперь мы берем число 3 и начнем возводить его в степени. Так, 30 = 1, по модулю 7 — тоже 1. 31 = 3, по модулю 7 — 3. 32 = 9, или 2 по модулю 7. 33 = 27, при делении на 7 дает 6. И так далее. Если мы построим такой ряд, мы увидим, что степени тройки дают, хотя и в другом порядке, всю систему вычетов по модулю 7, за исключением нуля: 1, 3, 2, 6, 4, 5.

Тем же свойством обладает и пятерка. А вот другие остатки от деления на 7 — 0, 1, 2, 4 и 6 — нет. По этой причине числа 3 и 5 называются первообразными корнями по модулю 7.

Первообразные корни существуют для каждого простого числа. Задавшись простым числом и первообразным корнем, мы можем зашифровать наше сообщение. Для этого мы записываем его в виде некоторого вычета по модулю нашего простого числа, а затем возводим первообразный корень в степень, равную нашему вычету. То, что получилось — некоторый новый вычет, и есть результат шифрования. Он передается нашему абоненту. Сделать все это довольно просто. А вот обратная задача — по зашифрованному сообщению, которое перехватил злоумышленник, восстановить исходное, — является гораздо более трудной. И она оказывается тем труднее, чем больше наше исходное простое число. Для ее решения даже при помощи современной техники может потребоваться столь большое время, за которое сама задача уже потеряет актуальность.

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

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