Самое большое на сегодняшний день простое число (2^213466917-1) обнаружено 20-летним канадцем Майклом Камероном - а вернее, его компьютером, участвующим в проекте распределенных вычислений Great Internet Mersenne Prime Search (GIMPS).

Простым числом называется натуральное число, которое делится только на единицу и на само себя. Понятно, что первые числа этого ряда вычисляются легко - 1, 2, 3, 5, 7, 11, 13, 17, 19, 23.... Но когда дело доходит до проверки на делимость чисел, состоящих из миллиона знаков, требуются годы машинного времени, если выполнять вычисления на одном компьютере.

Нормальному человеку сложно понять, какой прок в подобных числах. Однако для математиков и шифровальщиков поиск простых чисел иногда становится не только работой, но и увлечением всей жизни. Ярким примером здесь может служить история 28-летнего программиста Аарона Блоссера, работавшего на телефонную компанию US West. В 1998 году Блоссер подключил 2585 компьютеров своей компании к поиску очередного простого числа рекордного размера. Его грандиозный проект оставался незамеченным несколько месяцев, пока задержки на линиях US West не начали достигать нескольких минут - поскольку компьютеры, призванные обеспечивать переключение линий, занимались поиском простых чисел. "Когда я пришел на работу US West, вся эта вычислительная мощь просто искушала меня", - заявил Блоссер, когда к нему пришли из ФБР.

Что касается Майкла Камерона, то он нашел свое простое число 2^213466917-1, состоящее из 4053946 знаков, в рамках вполне законного проекта GIMPS. Проект основан в 1996 году Джорджем Уолтменом и посвящен поиску специальных простых чисел, называемых числами Мерсена. Французский монах Мартэн Мерсен (1588-1648) первым заметил, что если 2^p-1 - простое число, то и само P тоже простое. Поскольку числа Мерсена представляют собой степени двойки без единицы (3, 7, 31, 127...), а в компьютерах числа представляются как раз в двоичном коде, возникает простой алгоритм проверки таких чисел на делимость.

Всякий, кто желает поучаствовать в проекте GIMPS, скачивает себе программу, которая, как и в случае проекта SETI@Home, будет время от времени связываться с основным сервером PrimeNet, получать от него задание, выполнять его и передавать обратно результаты.

В настоящее время известно 39 чисел Мерсена. Последнее как раз и обнаружил Камерон, который в течение последних 45 дней в свободное от работы время запускал программу GIMPS на своем компьютере с процессором 800 MHz AMD. Однако понятно, что он не достиг бы такого результата, если бы не помощь всех остальных 130000 участников проекта распределенных вычислений, которые потратили на вычисление этого числа в общей сложности 13000 лет машинного времени (в обычном времени это два года параллельной работы тысяч компьютеров).

Кстати сказать, отыскивание новых простых чисел может принести не только математическую радость, но и приличную денежную награду. Вышеупомянутый хакер Аарон Блоссер в 1998 году охотился за 38-м числом Мерсена. И если бы не ФБР, то вполне возможно, именно он получил бы те 50 000 долларов, которые Electronic Frontier Foundation (EFF) учредил как награду за отыскание первого простого числа, имеющего более миллиона цифр. Эту награду получил в 2000 году участник проекта GIMPS Наян Хаджратвала из США, обнаруживший простоту числа 2^6972593-1.

А следующие награды EFF - 100 000, 150 000 и 250 000 долларов за простое число, соответственно, из десяти миллионов знаков, ста миллионов знаков и миллиарда знаков - еще ждут своих героев.

Copyright © 2000-2002 Нетоскоп www.netoscope.ru