Открыто новое рекордно большое простое число Мерсенна
Американские математики, участвующие в проекте 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.
Как сказано выше, теория чисел и, в частности, простые числа имеют вполне практическое и очень важное в современное время применение. Речь идёт о средствах защиты информации, в том числе посредством шифрования и дешифрования, а также кодирования сигналов.
Есть такая наука криптология — «наука о шифровании и дешифрованиии». Подробнее об этом, в т.ч. о применении простых чисел, можно узнать из следующих лекционных статей блога:
- Из истории криптологии
- Традиционные вопросы криптологии
- Криптоаналитические атаки
- Асимметричный алгоритм шифрования RSA: теоретические основы
- Асимметричный алгоритм шифрования RSA: практический пример работы
Комментарии:
В дополнение:
Оставить комментарий