Существует ли самое большое простое число
papyrus_net
πάπυρος
где-то далеко идут грибные дожди.
Математики назвали самое большое простое число, которое когда-либо было определено. 17,425,170 — именно столько цифр содержится в самом большом простом числе, открытом на днях американскими математиками.
Простое число – это натуральное число, которое без остатка делится только на себя и на единицу. Так вот, в самом длинном простом числе насчитали 17,425,170 цифр. Это число заменяет открытое в 2008 году простое число, у которого количество цифр составляло всего лишь 12,978,189.
Новое число было открыто математиками из Университета Центрального Миссури, США. Подсчеты проходили в рамках проекта Great Internet Mersenne Prime Search (GIMPS), являющийся широкомасштабным проектом добровольных вычислений, связанных с поиском простых чисел Мерсенна. Сама система представляет специально разработанное программное обеспечение, которое работает на тысячах компьютеров. При обнаружении самого большого простого числа проводится тщательная проверка, которая должна подтвердить, что число является простым. Компьютер с процессором на основе Intel i7, для примера, проверял на протяжении четырех с половиной суток, так что это действительно была непростая задача.
Прошлое самое большое простое число тоже нельзя было опубликовать в обычном издании; для сравнения, стандартная заметка на «Деталях мирах» насчитывает несколько тысяч знаков. Десять тысяч это уже большая статья, миллион знаков будет в книге, а миллиард, соответственно, небольшой библиотекой на тысячу томов. При печати убористым шрифтом самое большое простое число займет большой книжный шкаф, так что вряд ли кто-то решит переводить на это бумагу. Можно записать его в файл или воспользоваться изящной формой записи: рекордсмен в точности равен 257885161 — 1.
Числа вида 2N-1 еще называют числами Мерсенна по имени французского исследователя Марена Мерсенна, который описал их впервые еще в первой половине XVII века. Такие числа используются в программных генераторах псевдослучайных чисел — отсюда интерес к ним не только теоретиков, но и практиков. Большие простые числа также интересны специалистам по криптографии, поэтому организация Electronic Frontier Foundation даже утвердила награды в $50000, 100000, 150000 и 250000 за вычисление простых чисел с миллионом, десятью миллионами, ста миллионами и миллиардом знаков соответственно.
Число простых чисел бесконечно и это легко доказать: возьмем все уже посчитанные простые числа, перемножим их между собой и прибавим единицу. При делении на любой сомножитель мы по определению получаем единицу в остатке, так что это число не делится ни на одно из предыдущих простых чисел. И, тем более, оно не может делится на что-то еще, кроме самого себя: проблема только в том, что вычислять такие числа с определенного момента слишком сложно даже при помощи суперкомпьютеров.
А числа Мерсенна 2N-1 отличаются тем, что их заметно проще вычислять и вдобавок существует специальный тест, позволяющий быстро (по сравнению с перебором всех простых сомножителей) доказать их простоту; числа Мерсенна давно стали самыми большими простыми… но пока никто не может сказать, существует ли самое большое простое число Мерсенна; на сегодня из всего множества таких чисел известно лишь 48 простых чисел Мерсенна.
Открыто новое самое большое простое число
Международная коллаборация GIMPS заявила об открытии нового самого большого известного простого числа, в десятичной записи на миллион разрядов превосходящее предыдущее.
26 декабря 2017 года участники GIMPS (Great Internet Mersenne Prime Search), проекта добровольных вычислений по поиску простых чисел Мерсенна, подтвердили открытие нового самого большого простого числа. Привести его здесь невозможно, в десятичной записи оно состоит из 23 249 425 знаков; в книге с записью этого числа было бы около семи тысяч страниц.
Число, получившее обозначение M77232917, представляет собой степень двойки минус 1; показатель степени равен 77 232 917. Предыдущее самое большое известное простое число, открытое в январе 2016 года, было на миллион знаков короче.
M77232917 принадлежит к множеству чисел Мерсенна (M_n = 2^n – 1, где M и n — простые числа), названному в честь французского математика XVII века Марина Мерсенна. Как и все простые числа, числа Мерсенна нацело делятся только на самих себя и на единицу. Новооткрытое число стало 50-м по счету доказанным числом Мерсенна.
Крис Калдуэлл (Chris Caldwell), один из руководителей проекта GIMPS, удивлен, что новое рекордно большое простое число было найдено так скоро. «Обычно искать простые числа — все равно что находить дохлых кошек на дороге: они встречаются редко, и вы не ожидаете найти новую сразу после предыдущей», — объяснил он британской газете The Guardian.
Проект GIMPS использует вычислительные ресурсы компьютеров добровольцев со всего мира, чтобы искать большие простые числа. Во вторник, 26 декабря, компьютер 51-летнего электрика из штата Теннесси Джонатана Пейса, завершая шестидневный марафон вычислений, обнаружил число-кандидат; еще несколько дней ушло на то, чтобы подтвердить, что M77232917 удовлетворяет определению простого числа. На подтверждение результата у разных компьютеров ушло от 34 до 82 часов. Это первое простое число, вычисленное на компьютере Пейса за 14 лет участия в проекте; за его открытие владелец компьютера получит вознаграждение — три тысячи долларов.
Другим участникам проекта везет больше: например, Кертис Купер, математик из Университета штата Миссури, находил самые большие простые числа четыре раза, в последний раз в 2016 году. Предыдущие 14 самых больших простых чисел также были обнаружены участниками проекта GIMPS.
Новое самое большое простое число
Математик Кертис Купер (Curtis Cooper) из Университета Миссури в Уорренсберге нашел новое наибольшее простое число среди бесконечного ряда теоретически существующих. Оно равно (2 74207281 ) – 1 и содержит 22 338 618 цифр. Открытие сделано в рамках проекта GIMPS (Great Internet Mersenne Prime Search), посвященного именно этой теме, на сайте проекта и появилось сообщение.
Простые числа — это числа, которые делятся только на единицу и само себя, как, например, 2, 3, 7, 11, 13, 17 и так далее. Теорема о том, что множество простых чисел бесконечно была доказана еще Евклидом, а сейчас математики периодически называют самое большое из найденных простых чисел. До нынешнего открытия самым большим простым числом было (2 57885161 ) – 1. Выглядит похоже, но в нем на 5 миллионов цифр меньше, нашел его, кстати, также Кертис Купер.
Поиск простых чисел математики ведут с использованием алгоритма поиска так называемых чисел Мерсенна. Это числа в виде 2p – 1, где p — это тоже простое число. Всего на данный момент известно 49 простых чисел Мерсенна, причем порядковые номера с уверенностью установлены только у первых 44 из них, т.е. между четырьмя самыми большими могут найтись и другие простые числа.
Интересен и сам проект GIMPS. Это один из проектов, в котором задействованы добровольцы со всего мира. Они предоставляют проекту вычислительные мощности своих компьютеров ради поисков новых простых чисел Мерсенна.
Работа с большими простыми числами применяется в современной криптографии и для генерации псевдослучайных чисел. Однако, дать ответ на вопрос, зачем нужен поиск именно самых больших простых чисел, вряд ли удастся достаточно убедительно — математики работают над подобными задачами, не задаваясь их практической значимостью (впрочем, иногда она находится постфактум, спустя много лет).
Но сам по себе проект GIMPS уже оказался очень полезным. Сегодня многие рассматривают клиентскую программу проекта как прекрасный инструмент для тестирования стабильности работы аппаратной части компьютера. Пиковые нагрузки и жесткий контроль позволяют легко выявлять проблемы с памятью, кэшем, шиной данных, разгоном и перегревом процессора и т. п. Не так давно, к примеру, программа помогла найти ошибку в процессорах Intel Skylake, работающих при высокой загрузке.
Источники:
https://papyrus-net.livejournal.com/373744.html
https://pikabu.ru/story/otkryito_novoe_samoe_bolshoe_prostoe_chislo_5614258
https://scientificrussia.ru/articles/nazvano-novoe-samoe-bolshoe-prostoe-chislo
