Архивы: по дате | по разделам | по авторам

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

Архив
автор : Леонид Дурман   24.04.2001

Числа Ферма от Эйлера до наших дней

Числа Ферма от Эйлера до наших дней

Хотите войти в историю?

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

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

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

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

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

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

Простые числа будоражили воображение математиков с древнейших времен. Еще Евклид доказал, что простых чисел бесконечно много, но их распределение носит весьма неравномерный характер. Есть простые числа-близнецы, разность между которыми равна 2, но существуют сколь угодно большие промежутки, в которых простых чисел нет. Поэтому распределение простых чисел было названо заколдованным. Были предприняты попытки построить функции, значениями которых были бы только простые числа, но и таких функций пока нет 3. Можно доказать, что никакой многочлен с целыми коэффициентами не может для всех n (или для всех достаточно больших n) давать простые числа. Естественно рассмотреть показательные функции типа f(n) = anmbn, где a, b - целые. Для первого случая в этой формуле простые числа могут появиться лишь при a - b = 1 и простом показателе степени 4. Для a = 2, b = 1 получаются числа Мерсенна. Во втором случае 5 число an + bn может быть простым лишь тогда, когда n является степенью числа 2. Для a = 2, b = 1 получаются числа вида Fm = 22m = 1. Первым человеком, изучавшим эти числа, был величайший математик средневековья Пьер Ферма, и позже числа такого вида назвали в его честь. В частности, величайший математик средневековья Пьер Ферма изучал свойства чисел, задаваемых формулой Fm = 22m + 1, - чисел Ферма. В письме к своему другу и коллеге Мерсенну Ферма заметил, что при m = 0, 1, 2, 3, 4 (соответственно F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537) все эти числа являются простыми. Он считал, что F5 = 4294967297 тоже простое число, так как не смог найти для него делитель и попытался «догадаться», что все числа этого вида простые 6. Потребовалось 92 года и гений Леонарда Эйлера, чтобы опровергнуть это утверждение. Эйлер разложил F5 на множители 641 и 6700417. Ему было тогда 25 лет, и он любил разные вычислительные задачи. Но для достижения этого результата Эйлер действовал не вслепую 7, а доказал, что всякий делитель числа Ферма имеет вид k•2m+1 +1. Таким образом, он проверял всего десять делителей вида k•64 + 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица

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

[i39358]


1 (обратно к тексту) - «КТ» ##358, 359. Адрес SETI@Home: setiathome.ssl.berkeley.edu.
2 (обратно к тексту) - «КТ» #211 (1997 г.). Числа Мерсенна Mp = 2p - 1. Адрес проекта GIMPS: www.mersenne.org.
3 (обратно к тексту) - В Интернете существует распределенный проект, который занимается вычислением реальных значений функции pi(x) - количества простых чисел, не превосходящих x. Можно посмотреть на красивые диаграммы и поучаствовать: numbers.computation. free.fr/Constants/Primes/Pix/pixproject.html.
4 (обратно к тексту) - an - bn = (a - b)(an-1 + an-2b + … + bn-1)
5 (обратно к тексту) - a2n+1 - b2n+1 = (a + b)(a2n + a2n-1b + … + b2n)
6 (обратно к тексту) - Ни Мерсенн, ни Ферма не решали эту проблему, хотя могли бы. В том же 1640 году Ферма доказал свою малую теорему: Для всякого простого числа p и натурального x число xp-1 - 1 делится на p. Если не делится, следовательно, p не является простым числом. Используя эту теорему, Ферма мог бы проверить пятое число, выполнив всего 32 операции возведения в квадрат по модулю 232 + 1, получил бы число 3029026160 и этим доказал, что F5 составное, даже не находя его делителей.
7 (обратно к тексту) - В конце жизни великий Эйлер ослеп на один глаз от титанической вычислительной работы, которую сумел выполнить в рекордно короткий срок.
8 (обратно к тексту) - Сам Гаусс построил 17-угольник. Ришело на восьмидесяти страницах указал построение 257-угольника. В гёттингенской библиотеке в чемоданах больших размеров хранится способ построения правильного 65537-угольника, выполненного неким Гермесом. По этому поводу Джеймс Литлвуд пошутил: «Один навязчивый аспирант достал своего руководителя, и тот сказал ему:
- Идите и разработайте способ построения правильного 65537-угольника!
Аспирант ушел и вернулся только через двадцать лет.
9 (обратно к тексту) - Можно представить себе порядок: грубо говоря, n-e число Ферма это 2n-е число Мерсенна.

Люди, годы, делители.


Кто

Число найденных делителей
(в том числе в соавторстве).

Год, когда нашел первый делитель

Pierre Fermat

5 простых

1640

Leonard Euler

2

1732

Edouard Lucas

1

1877

Иван Михеевич Первушин

2

1877

Fortune Landry

2

1880

H. Le Lasseur

1

1880

Paul Seelhoff

1

1886

Allan Cunningham

3

1899

A.E.Western

5

1903

James Cullen

1

1903

J.C.Morehead

1

1906

Kraitchik

1

1925

John L. Selfridge

6

1953

Raphael M. Robinson

20

1956

John Brillhart

5

1962

Hans Riesel

1

1962

Claude P. Wrathall

11

1963

Michael A.Morrison

2

1970

John C. Hallyburton

2

1974

G. Matthew

2

1976

Hugh C. Williams

6

1976

D.E.Shippee

4

1977

Gary B.Gostin

60

1978

Wilfrid Keller

12

1978

Robert Baillie

5

1979

Philip B. McLaughlin

7

1979

Hiromi Suyama

7

1979

A.Oliver L.Atkin

5

1979

N.W.Rickert

5

1979

G.V.Cormack

4

1979

Richard P.Brent

8

1980

John M.Pollard

2

1980

Francois Morain

1

1988

Arjen K.Lenstra

2

1990

Mark S.Manasse

2

1990

Richard E. Crandall

5

1991

Harvey Dubner

8

1992

Jeffrey Young

8

1993

Tadashi Taura

16

1995

Karl Dilcher

1

1996

van Halewyn

1

1997

Demichel

1

1997

Yves Gallot

11

1997

Robert Prethaler

1

1998

Геннадий Гусев

1

1998

Richard McIntosh

1

1999

Claude Tardif

1

1999

Charles F. Kerchner III

3

1999

Dan Morenus

1

1999

John Renze

1

1999

John B. Cosgrave

1

1999

Rachel Lewis

1

2000

Леонид Николаевич Дурман

7

2000

Ray Ballinger

1

2000

Nestor Sergio de Araujo Melo

1

2000

Payam Samodoost

1

2000

Takahiro Nohara

1

2001

Peter Grobstich

1

2001


© ООО "Компьютерра-Онлайн", 1997-2024
При цитировании и использовании любых материалов ссылка на "Компьютерру" обязательна.