Мемуары о будущем

Дмитрий Беляев

Открыто новое рекордно большое простое число Мерсенна

Опубликовано: 8 февраля 2013 года


Рубрика: Дайджест, Лекции




Американские математики, участвующие в проекте GIMPS, получили самое большое известное простое число — оно состоит из 17 миллионов цифр, его открытие позволит получить новые стойкие шифры, говорится в сообщении на сайте проекта.

Новое простое число, относящееся к классу простых чисел Мерсенна, записывается как 2^57885161-1, в нем 17425170 цифр.

Оно было получено 25 января 2013 года на компьютере одного из участников проекта GIMPS — профессора университета центрального Миссури Кертиса Купера (Curtis Cooper).

На проверку простоты нового числа ушло 39 дней работы персонального компьютера в Университете Центрального Миссури, где работает Купер.

Независимая проверка была осуществлена сразу тремя исследователями на разных машинах, включая 32-ядерный сервер, предоставленный компанией Новартис.

Для Кертиса Купера новый рекорд стал уже третьим — ранее самые большие простые числа ему удавалось обнаруживать в 2005 и 2006 годах.

В 2008 году математики из Калифорнийского университета в Лос-Анджелесе побили рекорд Купера, открыв уже упоминавшееся простое число, записываемое 12 978 189 знаками.

За предыдущее открытие проект GIMPS получил премию в 100 тысяч долларов от фонда EFF, обещанную за открытие первого простого числа, записываемого более чем 10 миллионами знаков.

Полученные деньги проект разделил на небольшие премии для поощрения следующих открытий — так, Купер с 48-м числом Мерсенна претендует на 3 тысячи долларов.

Прежнее самое большое простое число, полученное в 2008 году, содержало 12978189 цифр.

«Простые числа очень интересны не только математикам, но и обычным людям, потому что они применяются в криптографии, например, для банковских кодов. Все они основаны на больших простых числах. Чем больше простое число, тем устойчивее шифр. Поэтому есть большой интерес к ним», — пояснил РИА Новости сотрудник Математического института имени Стеклова РАН (МИАН) Николай Андреев.

Проект GIMPS (Great Internet Mersenne Prime Search), созданный в 1996 году, представляет собой сеть распределенных вычислений, к которой может присоединиться любой желающий.

Его цель — поиск так называемых простых чисел Мерсенна, впервые описанных в 17 веке французским математиком Мареном Мерсенном. «Обычные» простые числа делятся без остатка только на самих себя и на единицу, а простые числа Мерсенна могут быть представлены в виде 2^p-1. Для нового числа этот показатель равен 57 885 161.

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

Для практических применений не важно, является ли простое число числом Мерсенна, но математикам так проще находить простые числа, там более простые алгоритмы», — сказал Андреев.

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

По материалам: РИА Новости и Lenta.ru

P.S.

Напомню, что простое число — это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя.

Все остальные натуральные числа, кроме единицы, называются составными. Таким образом, все натуральные числа больше единицы разбиваются на простые и составные. Изучением свойств простых чисел занимается теория чисел. В теории колец простым числам соответствуют неприводимые элементы.

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

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157…

Таким образом, последним известным на сегодняшний день простым числом в этом ряду и является открытое на днях число 2^57885161-1.

P.S.S.

Как сказано выше, теория чисел и, в частности, простые числа имеют вполне практическое и очень важное в современное время применение. Речь идёт о средствах защиты информации, в том числе посредством шифрования и дешифрования, а также кодирования сигналов.

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

0


1 звезда2 звезды3 звезды4 звезды5 звезд (Еще никто не голосовал)
Loading ... Loading ...
Google Bookmarks Digg Reddit del.icio.us Ma.gnolia Technorati Slashdot Yahoo My Web News2.ru БобрДобр.ru RUmarkz Ваау! Memori.ru rucity.com МоёМесто.ru Mister Wong





Записи с теми же метками:

Комментарии:


  1. Комментатор: Дмитрий Беляев

    В дополнение:

    Проще некуда // Найдено простое число длиной в пять романов «Война и мир»

    В начале февраля 2013 года математик Кертис Купер, участник проекта распределенных вычислений GIMPS (Great Internet Mersenne Prime Search), обнаружил 48-е простое число Мерсенна.

    Десятичная запись такого числа состоит из более чем 17 миллионов знаков. Для сравнения, в «Войне и мире» Толстого всего примерно 3,1 миллиона символов. За свое открытие профессор Университета Центрального Миссури вполне может получить три тысячи долларов. Впрочем, он, как и другие участники GIMPS, занимается поиском простых чисел Мерсенна вовсе не ради денег.

    Преданья старины глубокой

    Числа Мерсенна — это числа вида 2p — 1, где p — произвольное целое число, называемое показателем. Эти числа влекли математиков с древнейших времен, ориентировочно с Евклида (примерно 300 год до нашей эры), правда, до XVI века ученые полагали, что все эти числа простые, то есть делятся только на себя и единицу. Это, конечно же, неверно — достаточно взглянуть на четвертое число Мерсенна: оно равно 15 и представляется в виде произведения 3 и 5.

    По-видимому, первым, кто заметил, что не все числа Мерсенна с простыми показателями (известно, что для составных показателей число Мерсенна не может быть простым) являются простыми, был Худальрикус Региус в 1536 году. Он показал, что при p = 11 получившееся число — это 2047 — оказывается составным, поскольку представляется в виде произведения 23 и 89.

    В XVII веке поиск простых чисел Мерсенна стал довольно популярным среди математиков развлечением. В 1640 году к изучению этих чисел подключился знаменитый Пьер Ферма — он показал, что работы его предшественников, в которых утверждалась простота чисел для p = 23 и p = 37, были ошибочны.

    Но вообще, Ферма не был уникален в своем интересе к этому предмету, в истории этих чисел отметились многие известные ученые: Эйлер, Паскаль, Галилео, Гюйгенс.

    Имя же свое числа Мерсенна получили в честь французского монаха Марена Мерсенна, философа, теолога и математика.

    Он наткнулся на эти числа в поисках универсальной формулы, которая позволяла бы перечислять все простые числа.

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

    Впрочем, эта гипотеза стала популярной уже после смерти автора. Так часто бывает с некоторыми математическими утверждениями — по совершенно непонятной причине они оказываются в центре внимания множества математиков. Возможно, на руку ей сыграла, как и в случае с легендарной теоремой Ферма, простота формулировки.

    Как бы то ни было, но с рядом Мерсенна ученые разобрались только в середине XX века — тогда они установили, что список показателей, дающих простые числа Мерсенна и не превосходящих 257, выглядит следующим образом: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 и 127. Это и есть первые 12 простых чисел Мерсенна. Кстати, простоту числа Мерсенна для показателя 61 (оно равно 2 305 843 009 213 693 951) доказал российский математик Иван Первушин в 1878 году.

    Наше время

    Надо сказать, что победе над гипотезой Мерсенна способствовало появление так называемого теста Люка-Лемера.

    Суть его заключается в следующем: для фиксированного числа Мерсенна вычисляется некоторая рекурентная последовательность.

    Рекурентная формула для членов этой последовательности, во-первых, относительно проста, а во-вторых, для проверки требуется взять p — 2 члена последовательности, где p — нечетный простой показатель числа Мерсенна.

    Сложность работы алгоритма составляет порядка третьей степени log n, где n — само число Мерсенна. Использование разного рода методов быстрого умножения, как, например, метода Шёнхаге — Штрассена, позволяет немного ускорить работу, однако кардинально сложности не меняет.

    Формула для генерации простых чисел: множество неотрицательных значений этого многочлена от 26 переменных, для всевозможных наборов из 26 натуральных чисел дает все простые числа.

    Нужно понимать, что это крайне низкая вычислительная сложность, то есть алгоритм работает довольно быстро.

    Для сравнения, самый быстрый детерминистский алгоритм проверки простоты из существующих — тест Агравала-Каяла-Саксены c улучшениями Померанса-Ленстры — имеет сложность порядка (log n)6. Относительную простоту программирования и низкую вычислительную сложность теста Люка-Лемера ученые оценили только с появлением компьютеров.

    В 60-е годы прошлого века интерес к числам Мерсенна стал спадать. Связано это было с тем, что перспективы вычислительной техники на тот момент виделись довольно туманными, а использование суперкомпьютеров для поиска больших простых чисел казалось довольно расточительным.

    В 1968 году в Университете Иллинойса было открыто 23-е простое число Мерсенна с показателем 11213. На тот момент это было настолько великим достижением, что Пол Бейтман, который руководил кафедрой теории чисел в этом университете, заказал специальную печать для корреспонденции, на которой, помимо даты, красовалась надпись «211213 — 1 — простое число».

    В 1970-х годах интерес к числам Мерсенна снова активизировался. Причиной тому стала история двух тогда еще американских школьников — Лауры Никел и Лэндона Нолла.

    Не особо разбираясь в математических тонкостях вопроса, они написали программу для проверки чисел Мерсенна на простоту с помощью теста Люка-Лемера и прогнали ее на суперкомпьютере в местном университете. В результате они смогли найти 25-е и 26-е простые числа Мерсенна с показателями 21 701 и 23 209 соответственно. Это были самые большие простые числа из известных на тот момент. Нолл после этого стал обладателем еще одного рекорда — в 1989 году он принял участие в открытии самого большого простого числа, которое не является числом Мерсенна (это так называемое простое число Амдала 6, названное так в честь рабочей группы, открывшей его, и равное 391581*2216193-1).

    История с открытием школьников попала на телеэкраны, и поиск простых чисел Мерсенна снова вернулся в моду. Следующие успехи в этой деятельности были связаны с суперкомпьютерами Крэй — один из сотрудников компании-производителя Дэвид Словински написал программу для поиска простых чисел Мерсенна, работавшую на этих машинах, пока они не использовались.

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

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

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

    48-е по счету и небольшая премия

    Самым последним открытием в проекте GIMPS стало обнаружение 48-го простого числа Мерсенна. Это открытие было сделано математиком из Университета Центрального Миссури Кертисом Купером. На прогонку теста Люка-Лемера на одной из машин в университете у Купера ушло 39 дней. Его результат был перепроверен тремя независимыми пользователями, один из которых использовал 32-ядерный сервер, предоставленный компанией Новартис.

    Размеры нового числа потрясают — его запись в десятичной системе счисления состоит из 17 425 170 знаков. Для самого же Кертиса это открытие стало уже третьим — ранее самые большие простые числа ему удавалось обнаруживать в 2005 и 2006 годах.

    В 2008-м рекорд Кертиса был побит группой исследователей из Калифорнийского университета в Лос-Анджелесе. Они обнаружили простое число Мерсенна, в десятичной записи которого было 12 978 189 знаков.

    На момент открытия это число было 45-м простым числом Мерсенна, однако спустя некоторое время было открыто еще два простых числа, меньших этого (числа не всегда открываются в порядке возрастания), поэтому его номер в настоящее время — 47. Именно оно до открытия Купера было рекордсменом по размеру.

    За открытие GIMPS получил премию в 100 тысяч долларов от фонда EFF, обещанную за открытие первого простого числа, записываемого более чем 10 миллионами знаков. Полученные деньги проект разделил на небольшие премии для поощрения следующих открытий — так, Купер с 48-м числом Мерсенна претендует на три тысячи долларов.

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

    В заключение хочется упомянуть еще про одно замечательное свойство чисел Мерсенна. Число называется совершенным, если оно равно сумме всех своих собственных (то есть положительных и отличных от самого числа) делителей, включая 1. Например, 6 — совершенное, поскольку 6 = 3 + 2 + 1.

    Еще Евклид обнаружил, что число вида 2n — 1 (2n — 1) совершенно, если в скобках стоит простое число, то есть простое число Мерсенна с показателем n. Позже Леонард Эйлер доказал, что все четные совершенные числа имеют такой вид, где в скобках стоит простое число Мерсенна.

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

    Вместо заключения

    У пытливого читателя, разумеется, может возникнуть вопрос, зачем вообще нужен поиск простых чисел Мерсенна. Во-первых, вычислительные нагрузки, стоящие за тем же проектом GIMPS, уже не единожды использовались для тестирования вычислительных мощностей — хорошо известно, что Intel апробировала Pentium II и Pentium Pro именно на GIMPS.

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

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

    Источник

Оставить комментарий

:wink: :-| :-x :twisted: :) 8-O :( :roll: :-P :oops: :-o :mrgreen: :lol: :idea: :-D :evil: :cry: 8) :arrow: :-? :?: :!:

ВНИМАНИЕ! Все комментарии, содержащие явные оскорбления (в адрес автора статьи или собеседника-комментатора), спам и очевидную рекламу сторонних ресурсов, будут удалены. Также не рекомендуется злоупотреблять матом (такие сообщения будут отмодерированы или удалены).


Другие материалы: