Гонки по вертикали

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

Но ведь потенциал современных компьютеров гораздо выше. Обработка нажатий на клавишу или щелчка мыши занимает микросекунды, а остальное время процессор ничем не занят, превращая компьютер в дорогой нагревательный прибор. Можно даже сказать, что обычный PC 99% своей мощности не использует в течение всего срока эксплуатации.

«Компьютерра» не раз писала о распределенных проектах, позволяющих не только обогревать комнату, в которой стоит ваш компьютер, но и делать полезные вычисления параллельно основной работе. Известный проект SETI@Home ¹ ищет слабые сигналы от других миров и пытается сделать новые открытия в астрономии. Математический проект GIMPS ищет самые большие простые числа Мерсенна ² и даже предлагает крупный денежный приз в случае обнаружения нового простого числа Мерсенна. За пять лет работы этого проекта (при использовании десятков тысяч компьютеров во всем мире) найдено только четыре таких числа.

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

Дорогой читатель, надеюсь, вы не являетесь Геростратом, который поджег храм Артемиды, чтобы оставить свое имя в истории. Возможно, вы не Эйлер. Но все же вы хотите, чтобы ваше имя осталось в истории навечно? У вас есть шанс - помочь распределенному проекту «Поиск делителей для чисел Ферма». Проект создан русским человеком, автором этой статьи. И я попытаюсь подробно рассказать любителям математики и компьютеров об этой затее.

Эти непростые простые числа

Простые числа будоражили воображение математиков с древнейших времен. Еще Евклид доказал, что простых чисел бесконечно много, но их распределение носит весьма неравномерный характер. Есть простые числа-близнецы, разность между которыми равна 2, но существуют сколь угодно большие промежутки, в которых простых чисел нет. Поэтому распределение простых чисел было названо заколдованным. Были предприняты попытки построить функции, значениями которых были бы только простые числа, но и таких функций пока нет ³. Можно доказать, что никакой многочлен с целыми коэффициентами не может для всех n (или для всех достаточно больших n) давать простые числа. Естественно рассмотреть показательные функции типа f(n) = aⁿ•mbⁿ, где a, b - целые. Для первого случая в этой формуле простые числа могут появиться лишь при a - b = 1 и простом показателе степени ⁴. Для a = 2, b = 1 получаются числа Мерсенна. Во втором случае ⁵ число aⁿ + bⁿ может быть простым лишь тогда, когда n является степенью числа 2. Для a = 2, b = 1 получаются числа вида F_m = 2^2m = 1. Первым человеком, изучавшим эти числа, был величайший математик средневековья Пьер Ферма, и позже числа такого вида назвали в его честь. В частности, величайший математик средневековья Пьер Ферма изучал свойства чисел, задаваемых формулой F_m = 2^2m + 1, - чисел Ферма. В письме к своему другу и коллеге Мерсенну Ферма заметил, что при m = 0, 1, 2, 3, 4 (соответственно F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65537) все эти числа являются простыми. Он считал, что F₅ = 4294967297 тоже простое число, так как не смог найти для него делитель и попытался «догадаться», что все числа этого вида простые ⁶. Потребовалось 92 года и гений Леонарда Эйлера, чтобы опровергнуть это утверждение. Эйлер разложил F₅ на множители 641 и 6700417. Ему было тогда 25 лет, и он любил разные вычислительные задачи. Но для достижения этого результата Эйлер действовал не вслепую ⁷, а доказал, что всякий делитель числа Ферма имеет вид k•2^m+1 +1. Таким образом, он проверял всего десять делителей вида k•64 + 1.

В 1878 году Эдуард Люка (Lucas) усилил этот результат: каждый делитель числа Ферма имеет вид k•2^m+2 при некотором k.

Когда «королю математиков» Карлу Гауссу было всего девятнадцать лет, он доказал, что с помощью циркуля и линейки можно построить правильный N-угольник для простого N тогда и только тогда, когда N = F_m = 2^2m + 1 - простое число. Таким образом можно построить 3-, 5-, 17-, 257- и 65537-угольники ⁸.

Как видите, многие величайшие математики увлекались этими забавными числами. Увлечение это не пропало и сегодня, особенно с появлением компьютеров. А с приходом в нашу жизнь Интернета усилия людей разных стран стали совместными.

Числа Ферма и история

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

Чтобы доказать, что число Ферма не простое, существует два принципиальных способа.

1. Найти хотя бы один делитель.

2. Воспользоваться детерминированным тестом (Пепин, 1877).

Теорема. Число F_m простое тогда и только тогда, когда 3^{(Fm - 1)/2} + 1 делится на F_m.

В отличие от чисел Мерсенна числа Ферма растут невообразимо быстро ⁹. После Пьера Ферма простых чисел, носящих его имя, больше обнаружено не было. Но и найти делитель такого числа - весьма нетривиальная задача. Из-за большой редкости делителей и сложности их обнаружения каждый человек, нашедший новый делитель числа Ферма, попадает в историю математики. За три с половиной века поиска найдено немногим более 200 делителей. На сегодняшний день список их первооткрывателей включает 60 человек из разных стран мира.

Немецкий профессор Вилфрид Келлер (Wilfrid Keller) ведет официальную статистику всех известных делителей чисел Ферма. Существует несколько способов обнаружения простого делителя у числа Ферма. Самым простым, распространенным и достаточно эффективным способом является поиск по числам вида k•2ⁿ + 1 - тривиальное деление.

В 1855 году немецкий астроном Томас Клаусен в письме к Гауссу сообщил о разложении шестого числа Ферма F₆=274177•67280421310721, но этот факт более века оставался неизвестным: еще три человека независимо позже приходили к этому результату.

Уральский самоучка священник-математик Иван Михеевич Первушин прославился открытием трех чисел. В заявлении, датированном 25 сентября 1870 года, Первушин сообщает, что число Мерсенна 2⁶¹ - 1 - простое. На тот момент это было самое большое известное простое число, и его стали называть «числом Первушина». А в 1877-78 годах Первушин нашел делители для F₁₂ и F₂₃.

В 1903 году Вестерн (Western) за год титанической работы нашел пять новых делителей для различных чисел Ферма и сообщил, что у любого числа Ферма не существует еще неоткрытых делителей, меньших миллиона.

В докомпьютерную эпоху поиск этих чисел выливался в долгие недели и месяцы кропотливых вычислений. Один из самых внушительных ручных результатов получил в 1905 году Морхед (Morehead) - он нашел простое число 5•2⁷⁵ + 1, которое делит F₇₃ (последнее число имеет 2843147923723958851728 знаков, так что фактически записать его нет никакой возможности). Всего же ручным способом за три века было найдено лишь 16 делителей для чисел Ферма.

Рафаэль Робинсон (Raphael Robinson) в начале 1950-х нашел 20 делителей на одном из первых компьютеров SWAC. Это было одной из первых демонстраций превосходства электронных устройств над ручными вычислениями. Потомкам Робинсон оставил код програмы, который в несколько измененном виде использовался десятилетиями. Предварительно Робинсон опубликовал таблицу всех простых чисел вида k•2ⁿ + 1 для n < 1000 и k < 500, а потом среди этих простых чисел отыскал делители чисел Ферма.

Самым плодовитым искателем делителей для чисел Ферма является американский разработчик компьютерных систем Гэри Гостин (Gary Gostin), который на суперкомпьютерах разных времен нашел уже 60 делителей. В 1993 году он приостановил свои вычисления.

Таблица

Окончание следует

[i39358]