Последний рекорд землян — найдено самое длинное простое число
13 октября 2004
Рубрика: Обзоры и мнения.
Автор: .
pic
Всякий, кто изучает простые числа, бывает
очарован и одновременно ощущает собственное бессилие.
Определение простых чисел так просто и очевидно;
найти очередное простое число так легко;
разложение на простые сомножители — такое
естественное действие. Почему же простые
числа столь упорно сопротивляются нашим
попыткам постичь порядок и закономерности их
расположения? Может быть, в них вообще нет
порядка, или же мы так слепы, что не видим его?
(Ч. Узерелл. Этюды для программистов. М. Мир 1982)

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

Дело в том, что здесь задействованы так называемые распределенные вычисления, когда с помощью Интернета объединяются мощности тысяч компьютеров. Это дает возможность подступиться к задачам, требующим колоссальных вычислительных ресурсов. Самые популярные из них — поиск сигналов от внеземных цивилизаций, поиск формулы молекулы для лекарства от рака, вскрытие криптопротокола (это не взлом, а полуспортивная акция, всемирный конкурс по подбору ключа, участвует, например, команда журнала «Компьютера»), и, наконец, поиск простых чисел, точнее, простых чисел, попадающих под формулу Мерсенна. А вот, собственно, и сама новость.

15 мая появилось долгожданное сообщение. Участники проекта Great Internet Mersenne Prime Search (GIMPS http://www.mersenne.org/prime), основная цель которого заключается в поиске максимально длинных простых чисел, установили новый рекорд. В настоящее время результаты находятся на проверке, и если они подтвердятся, найденная цифровая последовательность станет сорок первым числом Мерсенна.

Около полугода назад активисты проекта GIMPS обнаружили последовательность, состоящую из 6320430 цифр и оказавшуюся сороковым числом Мерсенна. На сей раз искомый результат был выдан программой намного быстрее, поскольку количество участников проекта значительно выросло, а интервал между 41 и 40 числами Мерсенна оказался существенно короче интервала между 40 и 39.

Как сообщает (http://news.com.com/2100-7343_3-5215542.html?tag=nefd.top) CNET News, у сорок первого числа Мерсенна меньше 10 миллионов цифр, а на проверку результатов уйдет от двух до четырех недель. Кстати, счастливчик, который найдет последовательность из 10 млн. знаков, получит приз в размере 100 тысяч долларов США, учрежденный Фондом электронного фронтира (EFF). А за открытие простого числа, состоящего из 100 миллионов цифр, объявлена награда в 150 тысяч долларов.

Для любителей истории Сети и математики — в общем-то, нашей с вами истории, приведем предыдущие рекорды, совсем недавние.

Сообщение от 3 декабря 2003 года, 14:10. Студент Университета штата Мичиган Майкл Шейфер объявил об обнаружении самого длинного на сегодняшний день простого числа. Напомним, что простыми называются числа, делящиеся без остатка только на единицу и на самих себя. Результаты исследований в области поиска таких цифровых последовательностей могут найти широкое применение как в теории чисел, так и при разработке более стойких и надежных методов шифрования информации.

pic

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

Найденная выпускником Мичиганского университета последовательность состоит из 6320430 цифр и может быть записана как 220996011-1. На поиски ушли два года, а в расчетах были задействованы 211 тысяч компьютеров, предоставленных 60 тысячами добровольцев. Открытие было сделано еще 17 ноября, однако официально рекорд был признан только теперь, после проведения необходимых проверок. Интересно заметить, что решение задачи по поиску длинных простых чисел может принести и материальную выгоду. В частности, счастливчику, которому удастся обнаружить последовательность с 10 миллионами знаков, достанется премия в размере 100 тысяч долларов США. За нахождение же числа, состоящего из 100 миллионов цифр, объявлена награда в размере 150 тысяч долларов.

А если вернуться еще на два года, ту увидим, как весь мир обошла новость на эту же тему.

5 декабря 2001 года мир узнал самое большое из открытых до сих пор простых чисел Мерсенна. На письме его выражают цифрой 213466917-1. Если же писать его целиком, то в нем будет 4053946 знаков.

pic

Впрочем, это мало кого интересует: для того, чтобы полностью записать число, открытое 20-летним канадским студентом Майклом Кэмероном, уйдет три недели.

Майкл Кэмерон совершил свое открытие в рамках международного проекта GIMPS. Он, как и известный проект по поиску внеземного разума SETI, построен на разделении труда между подключенными к Интернету персональными компьютерами. К моменту открытия нового числа на GIMPS ушло уже 13 тысяч часов машинного времени, над решением одной задачи одновременно трудились 130 тыс. персональных компьютеров во всем мире. Для того, чтобы обнаружить новое число, Кэмерону пришлось следить за трудами своего 800-мегагерцового компьютера в течение 45 дней.

«О проекте GIMPS мне рассказал приятель, — говорит Майкл Кэмерон. — Он же сказал, что безрассудно зря тратить рабочее время процессора. Я подумал и решил: а ведь действительно машина по большей части простаивает — почему бы не использовать ее на благое дело? Я никак не ожидал, что найду новое простое число».

Большие простые числа используются в криптографии для шифрования данных. Знать их нужно и математикам-теоретикам.

Основатель программы GIMPS Джордж Волтман говорит: «Открытие Майкла Кэмерона — это самое интересное из того, чего нам удалось достичь. На работу над новым числом ушло два года, и теперь нам остается лишь поблагодарить всех участников проекта — а это 130 тысяч пользователей по всему миру».

Если вы захотели подключиться к проекту — посетите страничку http://vilenin.narod.ru/gimps.htm координатора команды русскоговорящих участников поиска чисел Мерсенна. На ней вы найдете инструкции по установке программного обеспечения и таблицу участников с затраченным на поиски временем в годах (в пересчете на условный процессор Р90). Стоит заняться, может, именно ваш компьютер найдет следующее число Мерсенна — прославитесь и разбогатеете. Не забудьте сослаться потом на журнал InfoCOM.UZ.

Orphus system
В Telegram
В Одноклассники
ВКонтакте