Числа Мерссена

[Иллидан]

Предлагаю выкладывать здесь, все что известно по Числам Мерсенна. Какие машины их ищут, какие программы используются для их поиска, какие алгоритмы для их нахождения существуют?

Определение. Если число 2^N−1 простое, то оно называется простым числом Мерсенна.

Например, 2^2−1 — первое простое число Мерсенна, 2^3−1 — второе, 2^11213−1 — 23-e, 2^216091−1 — 31-e.

Искать эти числа без компьютера довольно тяжело. Так, Эйлер в 1772 году нашёл 8-е число, 2^31−1, но после этого в течение 100 лет не было найдено ни одного! Лишь в 1876 Люк показал, что 2^127−1 — простое число. Но он нашел не 9-е, а сразу 12-е, так как 2^61−1, 2^89−1, 2^107−1 — тоже простые, но были найдены позднее. Новый прорыв случился лишь в 1950-х, когда с помощью вычислительной техники были найдены простые числа Мерсенна с показателями 521, 607, 1279, 2203, 2281. Все последующие числа Мерсенна были найдены с помощью ЭВМ. И для этого не нужно было быть великим математиком, в 1978 и 1979 годах студенты Нолл и Никел нашли 25-е и 26-е числа (21701 и 23209) на мэйнфрейме своего университета, чем и прославились на всю Америку. Но и у современных суперкомпьютеров есть пределы возможностей. Сегодня простые числа Мерсенна ищут десятки тысяч людей по всему миру, объединённые одним метапроектом GIMPS (Great Internet Mersenne Prime Search, www.mersenne.org). На счету GIMPS уже 8 самых больших простых чисел Мерсенна. Их показатели — 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951. 26972593−1 является 38-м простым числом Мерсенна, а про последние 4 ещё нельзя сказать, какие они по счету, т.к. ещё не все меньшие числа проверены. Эти же 4 числа являются самыми большими известными простыми числами.

Последнее число — 2^25964951−1 — было найдено 18 февраля 2005 года, оно состоит из 7816230 десятичных цифр, тот же, кто найдёт простое число более чем из 10 миллионов цифр, получит приз в $100000.

(Информация приведена по состоянию на март 2005)

[Виктор Смирнов]

разработал на delphi программу тестирования на простоту произвольных чисел Мерсенна вида 2^p-1 методом люка-лемера. Программа основана на представлении чисел в виде массивов 32-х разрядных элементов типа
cardinal, основные процедуры реализованы на ассемблере Delphi, реализация в windows xp. Получены следующие временные результаты тестирования чисел для степеней p (выборочно, просчитано до 216091):
< 9689 - менее 1 сек, 21701-59 сек, 23209 -1 мин 13 сек, 216091 - 15 час
58 мин. не могу найти аналоги, чтобы оценить скорость работы программы. Помогите определиться, заранее благодарен
Виктор Смирнов

[Blade]

А теперь объясните зачем вообще нужны эти числа? Какое у них практическое применение?

[JTG]

Сообщение от Blade

А теперь объясните зачем вообще нужны эти числа? Какое у них практическое применение?

Electronic Frontier Foundation назначило премию в 100 000 $ за нахождение простого числа длина которого превышает 10 млн. цифр, значит это кому-нибудь нужно
Криптография наверно или ещё какая-то хрень. Большие простые числа, например, в RSA используются.