Простые числа: история через века

«Простые числа созданы для того, чтобы их умножать»

Л. Д. Ландау

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

12 октября 2024 года Люк Дюран (Luke Durant, Сан-Хосе, Калифорния) обнаружил новое самое большое известное на сегодня простое число: 2¹³⁶²⁷⁹⁸⁴¹ – 1.

Оно было найдено в рамках проекта GIMPS (Great Internet Mersenne Prime Search). Это число состоит из 41 024 320 десятичных цифр. Если записать его в шестнадцатеричной системе счисления, то это будет цифра 1, за которой следуют 34 069 960 цифр F.

Оно принадлежит классу простых чисел Мерсенна (52-е число), которые являются крайне редкими — известно только 52 таких числа. Для поиска нового числа Дюран использовал программу распределённых вычислений, которая объединила тысячи серверов по всему миру. Его вычислительная система охватывала 24 региона дата-центров в 17 странах.

Цифр в числе на 16 миллионов больше, чем у предыдущего рекордсмена: с 2018 года самым большим простым числом считалось 2⁸²⁵⁸⁹⁹³³ − 1. Его обнаружил американский IT-специалист Патрик Лярош (Patrick Laroche). Десятичная запись этого числа состоит из 24 862 048 цифр. Это 51-е простое число Мерсенна.

Немного о простых числах. В России о них знает практически каждый школьник. Более того, в школьных экзаменах ОГЭ и ЕГЭ есть задачи на их применение. Им посвящены множество исследований и книг.

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

Простое число — натуральное число, имеющее ровно два различных натуральных делителя. О них знали ещё математики Древней Греции. Пифагор изучал простые (линейные) числа. Эратосфен изобрёл «решето Эратосфена»: алгоритм последовательного нахождения всех простых чисел от 1 до n. Евклид доказал, что множество простых чисел бесконечно.

Пьер Ферма (фр. Pierre de Fermat) высказал предположение, что все числа вида Fₙ = 2^(2ⁿ) + 1 являются простыми. При n = 0, 1, 2, 3, 4 числа Ферма простые и равны 3, 5, 17, 257, 65537.

Пока других простых чисел Ферма не обнаружено, и неизвестно, существуют ли простые числа при n > 4 или же все остальные числа Ферма — составные.

Французский математик Марен Мерсенн (фр. Marin Mersenne) предположил, что числа Mₙ = 2ⁿ − 1 , где n — простое, также простые числа (числа Мерсенна). Проверка верности предположения была намного выше возможностей того времени. Только в XX веке было обнаружено, что гипотеза была ложной.

Тем не менее, числа Мерсенна давно удерживают рекорд как самые большие известные простые числа.

Долгое время простые числа считались малоприменимыми за пределами чистой теоретической математики. Ситуация изменилась в 1970-е годы, после появления систем криптографии с открытым ключом, в которых простые числа составили основу первых алгоритмов шифрования, таких как RSA (аббревиатура от фамилий Rivest, Shamir и Adleman).