Cамое большое известное простое число теперь состоит из 17 425 170 цифр. В начале февраля 2013 года побит рекорд, продержавшийся четыре года. Для сравнения, в «Войне и мире» Толстого всего примерно 3,1 миллиона символов.

2 в степени 57 885 161 минус 1 – это третий рекорд, принадлежащий профессору из Университета Центрального Миссури Кертису Куперу. Он – доброволец широкомасштабного интернет-проекта по поиску простых чисел Мерсенна GIMPS (Great Internet Mersenne Prime Search).

 

Первое самое большое простое число Кертис открыл в 2005 году, затем в 2006 году он обновил свой рекорд. В 2008 году его достижение превзошли в Калифорнийском университете в Лос-Анджелесе. И вот,  через четыре года, Кертис Купер снова стал обладателем рекорда.

Найденное в августе 2008 года число M43112609=243112609-1 содержит 12 978 189 десятичных цифр и является первым известным простым числом, состоящим более чем из 10 миллионов цифр, что позволило GIMPS получить премию в 100 000 долларов США.

За нахождение простых чисел соответственно из более чем 100 и 1000 миллионов десятичных цифр Electronic Frontier Foundation обещаны аналогичные призы в $150 тыс. и $250 тыс.

Однако, чтобы получить следующую премию в 150 000 долларов США, придётся проверять на простоту числа из более чем 100 миллионов десятичных цифр, каждое из которых при текущем развитии вычислительной и алгоритмической техники потребует более трёх лет.

Кроме денежного вознаграждения, имя открывателя навсегда будет записано в анналы математики.

Эвристические оценки показывают, что существуют ещё четыре неизвестных простых числа Мерсенна, состоящие менее чем из 100 миллионов десятичных цифр.

На подтверждение открытия ушло 39 дней безостановочных вычислений на одном из университетских компьютеров. Пока для проекта никто не сделал больше, чем Купер и его университет. Всего же в GIMPS участвуют компьютеры, общее количество процессорных ядер которых составляет 360 тысяч, а суммарная мощность – 150 триллионов операций в секунду. Купер и его вуз получат премию в размере 3 тысячи долларов.

Открытое число принадлежит к довольно редкому классу простых чисел Мерсенна, которые имеют вид «2 в степени, выраженной натуральным числом, минус 1». Новое рекордное число — лишь 48-е известное науке число этого класса. После каждого открытия поиск нового числа усложняется.

Проект GIMPS основан в 1996 году. В рамках проекта открыты все 14 наибольших чисел Мерсена. Для их поиска добровольцы могут установить на своем компьютере бесплатную программу.

Новое число также проверяли с помощью разных программ, запущенных на различных компьютерах, чтобы избежать ошибок.

Числа Мерсенна — числа вида Mn = 2n — 1, где n — натуральное число. Названы в честь французского математика Марена Мерсенна (8 сентября 1588 — 1 сентября 1648).

Последовательность чисел Мерсенна:

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, ... (последовательность A000225 в OEIS)

Иногда числами Мерсенна называют числа с простыми индексами p. Эта последовательность начинается так:

3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607, 536870911, 2147483647, 137438953471, 2199023255551, 8796093022207, 140737488355327, 9007199254740991, 576460752303423487, 2305843009213693951, 147573952589676412927, 2361183241434822606847, … (последовательность A001348 в OEIS)

Простые числа Мерсенна

Числа Мерсенна получили известность в связи с эффективным критерием простоты Люка — Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые большие известные простые числа.

Длина M43112609 составляет 12978189 десятичных цифр, что позволило GIMPS в 2009 году получить премию в 100000 долларов США, назначенную сообществом Electronic Frontier Foundation за нахождение простого числа, десятичная запись которого содержит не менее 10 миллионов цифр.

Теперь известно 48 простых чисел Мерсенна, причём порядковые номера с уверенностью установлены только у первых 42. Интересно отметить, что 46-е найденное простое число Мерсенна было найдено на две недели позднее 45-го найденного простого числа Мерсенна и оказалось меньше его.

Последовательность простых чисел Мерсенна и их показателей начинается так:

Mp: 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, 162259276829213363391578010288127, 170141183460469231731687303715884105727, … (последовательность A000668 в OEIS)

p: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, … (последовательность A000043 в OEIS)

Список всех известных простых p, для которых M (p) (M (p) = 2p-1) является простым числом Мерсенна (P (p) – четное совершенное число; P (p) = 2p-1(2p-1)):

p
(exponent)

цифр
в Mp

цифр
в Pp

Год

Кто совершил открытие

1

2

1

1

----

----

2

3

1

2

----

----

3

5

2

3

----

----

4

7

3

4

----

----

5

13

4

8

1456

anonymous

6

17

6

10

1588

Cataldi

7

19

6

12

1588

Cataldi

8

31

10

19

1772

Euler

9

61

19

37

1883

Pervushin

10

89

27

54

1911

Powers

11

107

33

65

1914

Powers

12

127

39

77

1876

Lucas

13

521

157

314

1952

Robinson

14

607

183

366

1952

Robinson

15

1279

386

770

1952

Robinson

16

2203

664

1327

1952

Robinson

17

2281

687

1373

1952

Robinson

18

3217

969

1937

1957

Riesel

19

4253

1281

2561

1961

Hurwitz

20

4423

1332

2663

1961

Hurwitz

21

9689

2917

5834

1963

Gillies

22

9941

2993

5985

1963

Gillies

23

11213

3376

6751

1963

Gillies

24

19937

6002

12003

1971

Tuckerman

25

21701

6533

13066

1978

Noll & Nickel

26

23209

6987

13973

1979

Noll

27

44497

13395

26790

1979

Nelson & Slowinski

28

86243

25962

51924

1982

Slowinski

29

110503

33265

66530

1988

Colquitt & Welsh

30

132049

39751

79502

1983

Slowinski

31

216091

65050

130100

1985

Slowinski

32

756839

227832

455663

1992

Slowinski & Gage et al.

33

859433

258716

517430

1994

Slowinski & Gage

34

1257787

378632

757263

1996

Slowinski & Gage

35

1398269

420921

841842

1996

Armengaud, Woltman,
et al. (GIMPS)

36

2976221

895932

1791864

1997

Spence, Woltman,
et al. (GIMPS)

37

3021377

909526

1819050

1998

Clarkson, Woltman, Kurowski
et al. (GIMPS, PrimeNet)

38

6972593

2098960

4197919

1999

Hajratwala, Woltman, Kurowski
et al. (GIMPS, PrimeNet)

39

13466917

4053946

8107892

2001

Cameron, Woltman, Kurowski
et al. (GIMPS, PrimeNet)

40

20996011

6320430

12640858

2003

Shafer, Woltman, Kurowski
et al. (GIMPS, PrimeNet)

41

24036583

7235733

14471465

2004

Findley, Woltman, Kurowski
et al. (GIMPS, PrimeNet)

42

25964951

7816230

15632458

2005

Nowak, Woltman, Kurowski
et al. (GIMPS, PrimeNet)

??

30402457

9152052

18304103

2005

Cooper, Boone, Woltman, Kurowski
et al. (GIMPS, PrimeNet)

??

32582657

9808358

19616714

2006

Cooper, Boone, Woltman, Kurowski
et al. (GIMPS, PrimeNet)

??

37156667

11185272

22370543

2008

Elvenich, Woltman, Kurowski
et al. (GIMPS, PrimeNet)

??

42643801

12837064

25674127

2009

Strindmo, Woltman, Kurowski
et al. (GIMPS, PrimeNet)

??

43112609

12978189

25956377

2008

Smith, Woltman, Kurowski
et al. (GIMPS, PrimeNet)

??

57885161

17425170

34850339

2013

Cooper, Woltman, Kurowski
et al. (GIMPS, PrimeNet)

Эти числа влекли математиков с древнейших времен, ориентировочно с Евклида (примерно 300 год до нашей эры).

Числа Мерсенна названы в честь французского монаха Марена Мерсенна, философа, теолога и математика. Он наткнулся на эти числа в поисках универсальной формулы, которая позволяла бы перечислять все простые числа. В 1648 году он выпустил труд Cogitata Physica-Mathematica, в котором высказал предположение, что числа вида 2p — 1 должны быть простыми для показателей 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 и составными для всех остальных целых чисел, не превосходящих 257. Откуда взялась такая гипотеза, доподлинно неизвестно — современники сомневались, что Мерсенн мог разобрать все эти случаи вручную, да и он сам, говорят, это признавал.

Из-за простоты формулировки эта гипотеза стала популярной уже после смерти автора.

В 1970-х годах интерес к числам Мерсенна снова активизировался. Причиной тому стала история двух тогда еще американских школьников — Лауры Никел и Лэндона Нолла. Не особо разбираясь в математических тонкостях вопроса, они написали программу для проверки чисел Мерсенна на простоту с помощью теста Люка-Лемера и прогнали ее на суперкомпьютере в местном университете. В результате они смогли найти 25-е и 26-е простые числа Мерсенна с показателями 21 701 и 23 209 соответственно. Это были самые большие простые числа из известных на тот момент.

Поиск простых чисел Мерсенна снова вернулся в моду после того, как с телеэкранов была поведана история с открытием школьников. Современный облик этот процесс приобрел при помощи программиста Джорджа Уолтмана, в 1995 году создавшего проект распределенных вычислений GIMPS (Great Internet Mersenne Prime Search).

Проект, предназначенный для работы на i386, к концу первого года существования насчитывал уже более тысячи участников. Это был первый исследовательский проект распределенных вычислений в истории. Первое простое число Мерсенна (в настоящее время в рамках проекта открыто уже 14 штук) стало известно в 1996 году. Сейчас программу, работающую под всеми основными операционными системами, может установить себе любой желающий. Суммарная вычислительная мощность проекта к концу 2012 года составляла уже 95 терафлопс.

Применение

Большие простые числа используются в криптографии с открытым ключом. Простые числа также используются в хеш-таблицах и для генерации псевдослучайных чисел (в частности, в ГПСЧ «Вихрь Мерсенна»).

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

Использованы материалы

newfacts.info

Tags: , ,

Эта статья была опубликована: Воскресенье, марта 3, 2013 в 12:32 в категории Наука. Вы можете читать любые ответы через RSS 2.0 feed. You can leave a response, or trackback from your own site.

Ваш комментарий

Имя (*)
email (*)
вебсайт
Комментарий
Перед отправкой формы:
Human test by Not Captcha