Алексей Андреев
Самое большое на сегодняшний день простое число (2213466917-1) обнаружено 20-летним канадцем Майклом Камероном — а вернее, его компьютером, участвующим в проекте распределенных вычислений Great Internet Mersenne Prime Search (
Простым числом называется натуральное число, которое делится только на единицу и на само себя. Понятно, что первые числа этого ряда вычисляются легко — 1, 2, 3, 5, 7, 11, 13, 17, 19, 23…. Но когда дело доходит до проверки на делимость чисел, состоящих из миллиона знаков, требуются годы машинного времени, если выполнять вычисления на одном компьютере.
Нормальному человеку сложно понять, какой прок в подобных числах. Однако для математиков и шифровальщиков поиск простых чисел иногда становится не только работой, но и увлечением всей жизни. Ярким примером здесь может служить история 28-летнего программиста
Что касается Майкла Камерона, то он нашел свое простое число 2213466917-1, состоящее из 4053946 знаков, в рамках вполне законного проекта GIMPS. Проект основан в 1996 году Джорджем Уолтменом и посвящен поиску специальных простых чисел, называемых числами Мерсена. Французский монах Мартэн Мерсен (1588-1648) первым заметил, что если 2p-1 — простое число, то и само P тоже простое. Поскольку числа Мерсена представляют собой степени двойки без единицы (3, 7, 31, 127…), а в компьютерах числа представляются как раз в двоичном коде, возникает простой алгоритм проверки таких чисел на делимость.
Всякий, кто желает поучаствовать в проекте GIMPS, скачивает себе программу, которая, как и в случае проекта SETI@Home, будет время от времени связываться с основным сервером
В настоящее время известно 39 чисел Мерсена. Последнее как раз и обнаружил Камерон, который в течение последних 45 дней в свободное от работы время запускал программу GIMPS на своем компьютере с процессором 800 MHz AMD. Однако понятно, что он не достиг бы такого результата, если бы не помощь всех остальных 130000 участников проекта распределенных вычислений, которые потратили на вычисление этого числа в общей сложности 13000 лет машинного времени (в обычном времени это два года параллельной работы тысяч компьютеров).
Кстати сказать, отыскивание новых простых чисел может принести не только математическую радость, но и приличную денежную награду. Вышеупомянутый хакер Аарон Блоссер в 1998 году охотился за 38-м числом Мерсена. И если бы не ФБР, то вполне возможно, именно он получил бы те 50 000 долларов, которые Electronic Frontier Foundation (EFF) учредил как награду за отыскание первого простого числа, имеющего более миллиона цифр. Эту награду получил в 2000 году участник проекта GIMPS Наян Хаджратвала из США, обнаруживший простоту числа 26972593-1.
А
ССЫЛКИ ПО ТЕМЕ |
МАТЕРИАЛЫ ПО ТЕМЕ |
Физики строят высокоскоростную p2p-сеть — 22.11.01
У проекта Seti@Home кончились инопланетяне — 09.10.01
Суперкомпьютер от HP из 225 персоналок — 08.10.01
15 лет тюрьмы и 59 центов штрафа в секунду — за скринсейвер — 30.07.01
Intel делает суперкомпьютер для системы распределенных вычислений на основе peer-to-peer — 04.04.01