Max Home IndustryС простыми числами Мерсенна легче работать, чем с общими простыми числами, но последнее, 48-е из известных, имеет более 17 миллионов десятичных цифр — большие по любым меркам.
Простое число Мерсенна имеет форму 2p-1, и до недавнего времени мы знали только о 47 из них.
Можно показать, что если p не является простым числом, то 2p-1 не может быть простым числом, поэтому некоторые определения включают условие, что p является простым числом. Конечно, если вы ищете простые числа Мерсенна, вам нужно только проверить простые значения p. Однако проблема заключается не столько в создании возможного простого числа Мерсенна, сколько в том, что оно является простым числом при тестировании.
Марин Мерсенн 1588-1648
Первые несколько значений формы 2p-1, то есть 3,7,31,127, легко доказать как простые, потому что вы можете проверить их с помощью деления, но большие значения p быстро генерируют очень большие числа, проверка которых займет слишком много времени при попытке деления. по всем возможным факторам.
Хорошая новость заключается в том, что для простого числа Мерсенна существует быстрый тест, называемый тестом простоты Лукаса – Лемера.
Это означает, что 2p-1 с простым p является простым числом только в том случае, если оно делит Mp-2, где Mp порождается из ряда
Ск = С2к-1- 2
с S0 = 4.
Как видите, это намного проще, чем проверка всех факторов. Фактически, это намного проще, чем проверка общего числа на простоту, что десять наибольших известных простых чисел являются простыми числами Мерсенна.
Последний был обнаружен Кертисом Купером, математиком из Университета Центрального Миссури. Он обнаружил, что 48-е простое число Мерсенна составляет 257 885 161-1 (число с десятичными 17 425 170 цифрами) в результате поиска, выполненного сетью серверов GIMPS.
GIMPS, проект распределенных вычислений, предназначенный для поиска простых чисел Мерсенна, также отвечает за обнаружение 10 самых больших простых чисел Мерсенна, при этом предыдущее, 47-е, было обнаружено в 2008 году. Программное обеспечение GIMPS работает примерно на 1000 университетских компьютерах и доказывает, что текущие find was prime потребовало 39 дней вычислений на одной машине. Затем доказательство было проверено на 32-ядерном сервере за 6 дней.
Открытие имеет право на получение приза в 3000 долларов от проекта GIMPS, но этого недостаточно для призов Electronic Frontier Foundation в размере 150 000 и 250 000 долларов за открытие первого простого числа с не менее чем 100 миллионами и миллиардом цифр соответственно.
В чем суть?
Что ж, если вы математик, вам не нужна «точка», понятная другим людям. Но есть что-то странное в том, как вы можете взять 2 и умножить его на себя несколько раз, чтобы получить то, что должно быть очень факторизуемым числом, а затем, убрав единицу из результата, картина настолько изменится, что у нас есть простое число с нет факторов.
Также стоит отметить, что с точки зрения программирования простые числа Мерсенна очень просты. Например, в двоичном формате первые три — это 11, 111, 11111 и так далее.
В общем, 2p-1 — это просто двоичное число с p единицами. Тот факт, что у нас есть простые числа Мерсенна для p = 31, 61 и 127, часто очень полезен, когда вам быстро нужно большое простое число.
Наконец, доказать, что 48-е простое число Мерсенна не выходит за пределы вашей досягаемости, Programming Praxis предлагает вам задачу и решение — сгенерировать все 17 миллионов с лишним цифр. Оказывается, простой C не может этого сделать, но он находится в пределах досягаемости арифметической библиотеки множественной точности GNU, которая доставляется туда за несколько минут.