Наибольшее простое число-2024
Два в степени сто тридцать шесть миллионов двести семьдесят девять тысяч восемьсот сорок один. Минус один.
Это новое самое большое простое число.
Руководство некоммерческого проекта по поиску простых чисел GIMPS (Great Internet Mersenne Prime Search) объявило об обнаружении нового рекордно большого простого числа (то есть того, что делится только на себя и единицу). Им оказалось число 2¹³⁶ ²⁷⁹ ⁸⁴¹ − 1, то есть два в степени 136 279 841 минус единица. Запись рекордного числа не степенной, а в обычной десятичной форме кончается на …9486871551 и требует 41 024 320 цифр - архив с ними можно скачать по ссылке на сайте проекта, он сам по себе занимает около 20 мегабайт.
Новое самое большое простое число было найдено исследователем и бывшим сотрудником Nvidia Люком Дюрантом. Для его поиска энтузиаст развернул собственный вычислительный кластер в облаке. При этом расчеты проводились не на процессорах, а на видеокартах.
Как сообщается на сайте GIMPS, первый результат поиска, свидетельствующий о высокой вероятности того, что новое число действительно является простым, Дюрант получил 11 октября. На следующий день исследователь убедился в результате с помощью контрольного алгоритма (теста Люка - Лемера) - тот однозначно подтвердил простоту найденного числа. Затем результат Дюранта был перепроверен несколькими экспертами с помощью разных программ, реализующих тот же алгоритм, причем вычисления проводились как на графических картах, так и на обычных процессорах. 21 октября GIMPS официально объявила об открытии нового числа.
Как и подавляющее большинство рекордно больших простых чисел, открытых за последние столетия, новое число относится к числам Мерсенна, то есть может быть представлено в форме степеней двойки за вычетом единицы. Французский математик Марен Мерсенн внес значительный вклад в исследование простых чисел в XVII веке, хотя сами числа обсуждались еще древними греками.
Самые первые числа Мерсенна - это 1, 3, 7, 15, 31 и 63, то есть 2¹−1, 2²−1, 2³−1, 2⁴−1, 2⁵−1, 2⁶−1 и так далее. Как видно, не все они являются простыми - 1, 15 и 63 к ним не относятся. Кроме того, не все простые числа являются числами Мерсенна, - например, 11, 13 и 17 в форме степени двойки представить нельзя.
Тем не менее числа Мерсенна действительно превалируют в историческом ряду рекордсменов - прежде всего потому, что их поиск существенно легче, чем поиск простых чисел другого типа. Для чисел Мерсенна существует наиболее быстрый и эффективный алгоритм проверки - тот самый тест Люка - Лемера, сформулированный Эдуардом Люка в 1878 году и доказанный Диком Лемером в 1930-м. Сложность проверки простоты числа с помощью этого теста при этом растет с квадратом длины числа в двоичном представлении, поэтому поиск все новых простых чисел требует кратного увеличения вычислительных ресурсов.
Сейчас поиск новых рекордно больших простых чисел преимущественно проводится не университетскими математиками, а волонтерами GIMPS. В результате полтора десятка рекордов за последние десятилетия принадлежат именно этому сетевому сообществу. Простые числа широко используются в некоторых важных современных алгоритмах шифрования (например, RSA), и в этом смысле они имеют конкретное практическое применение. Однако это не касается рекордно больших простых чисел с миллионами разрядов в десятичной записи, они для криптографии не нужны. Их поиск - задача прежде всего эстетическая, хотя в прошлом она и дала несколько важных результатов в теории алгоритмов и компьютерных науках.
Источник публикации