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

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

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

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

Продолжение. Начало в #393

Один из ярых охотников за числами Ферма японец Тадаси Таура (Tadashi Taura) открыл 16 делителей. Он так увлечен этим занятием, что собирает самую разнообразную компьютерную технику и объединяет ее в немыслимый вычислительный центр на дому. (Думаю, его мощность порядка 20-30 гигафлоп. Это уже близко к очень серьезным вычислительным станциям.) Есть и другие искатели, работающие в одиночку (часто на своих собственных программах) или переписывающиеся только с теми, кого знают.

Тест Пепина (см. выше) применялся в том случае, если невозможно было обнаружить обычным делением хотя бы один делитель. В 1905-м и 1909 году Морхед доказывает этим способом, что F7 и F8 не являются простыми, но ни один делитель ему не был известен. Проделанная работа, например, для F8 была гигантской: Морхед 256 раз возводил в квадрат 78-значное число и находил остаток от его деления на другое большое число. Быстро ли вы, уважаемый читатель, сможете найти вручную остаток от деления 3485653281 на F4 = 65537? А ведь последнее имеет всего пять знаков…

Самое масштабное применение теста Пепина состоялось в 1999 году. Было задействовано большое количество мощных компьютеров, использован современный FFT-алгоритм (Fast Fourier Transformer - быстрое преобразование Фурье) умножения больших чисел и сложнейшие методы оптимизации. Вычисления, занявшие двести дней, дали ответ: F24 не является простым 1.

Профессор Ричард Крендал (Richard Crandall), руководивший вычислениями, сказал: «На любой современной технике подобные расчеты для F31 (646456993 знаков) займут как минимум десять тысяч лет. Это как раз до следующего ледникового периода. Но наряду с ростом мощности компьютеров находятся более совершенные способы проверки. И все же число F31 так велико, что в ближайшие двадцать лет мы не сможем сказать о нем ничего определенного». Сведущие люди шутят, что найти делитель для этого числа сложнее, чем слетать на Луну, если, конечно, оно не простое.

В 1970 году Моррисон (Morrison) и Бриллхарт (Brillhart) смогли разложить на множители F7 = (116503103764643•29 + 1) • (11141971095088142685•29 + 1), использовав вместо деления последовательный метод разложения цепной дробью. Десять лет спустя Ричард Брент (Richard P. Brent) и Джон Поллард (John M. Pollard) разложили на множители F8, применив так называемый Rho-метод Полларда. В 1990 году был получен еще более удивительный результат. Ленстра (Lenstra), Манасс (Manasse) и большая группа математиков, используя семьсот рабочих станций Sun в течение нескольких недель с применением метода решета числового поля, разложили F9, один из делителей которого имеет вид:

362128936829849024182024971631805407255830459520
272960891514314523640507570656742232821636569307•211 + 1.

Такой результат, конечно, не может быть получен тривиальным способом вообще никогда.

В 1995 году Брент сумел разложить F10, применив метод эллиптических кривых (Elliptic curve factoring method - ECM). Один из найденных им множителей F10 имеет 252 десятичных знака.

На сегодняшний день мы знаем судьбу всех чисел Ферма до F32 включительно. Для большинства из этих чисел известны также их делители, кроме m = 14, 20, 22, 24. Для разложения больших чисел наилучшим пока является ECM, тесно связанный со стойкой криптографией и находящийся на переднем крае математической науки.

Вы также можете принять участие в обнаружении новых делителей для малых Ферма чисел m < 24 и даже побороться за денежные призы 2. Но начиная с n = 25, ECM-алгоритм не может использоваться, так как приходится иметь дело со многими миллионами знаков.

«Новые ферматисты»: проект www.fermatsearch.org

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

До 1997 года не было каких-либо объединенных усилий по поиску больших «не Мерсенна» 3 чисел. Но француз Ив Галло (Yves Gallot) написал отличную программу Proth.exe 4, которая может находить огромные простые числа на самых обычных PC. После этого последовал буквально взрыв в этой области исследований. Программа Галло стала лучшей и очень популярной. Большинство рекордных простых чисел, найденные (на суперкомпьютерах) до появления Proth.exe, сегодня не входят даже в сотню. Программа, в частности, может находить и делители для чисел Ферма. За три года поиска ею найдено еще одиннадцать новых делителей для очень больших чисел Ферма.

В начале 2000 года я заметил, что ECM-проект охватывает малые числа. Поиск при помощи Proth забрался высоко в небо. А кто же сегодня работает над средними числами Ферма? Я знал только о японце Тауре, который бороздит это пространство, собирая неплохой урожай. Но свою программу он не публикует, а программа Галло эффективна только для больших чисел. Тогда я взял в руки карандаш и прикинул возможности. Бог мой! Да ведь шустрая программка на ассемблере для современных процессоров сможет реально поднять планку и обнаружить делитель. Первая рабочая версия программы была готова в апреле. Я назвал ее «Fermat» в честь первооткрывателя этих чисел.

По умолчанию программа работает при самом низком приоритете, давая возможность забирать ресурсы любому другому приложению. Я старался сделать массив, используемый в программе, как можно компактнее, не выходя за рамки второго кэша, а код оптимизировать под современные процессоры. Тесты показали, что на Celeron и Pentium III программа бежит практически одинаково (на той же частоте), что редко можно встретить у программ-монстров.

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

Неожиданно стали поступать письма с просьбой дать программку для исследования «16-й догадки Риверы» 5 и для поиска делителя F31. Я поместил в Интернете свою программу и информацию о проделанной работе. Моя Web-страничка начала обрастать информацией, а программа Fermat заняла свободную нишу как самая быстрая программа для поиска средних чисел Ферма.

Первыми участниками проекта стали почти все искатели, работавшие до тех пор раздельно, а так же системные администраторы и программисты. В конце 2000 года на авансцену возвратился главный «пожиратель» чисел Ферма Гари Гостин с тремя суперкомпьютерами от Hewlett-Packard. И на сегодня он в десять раз превосходит по компьютерной мощи всех остальных участников вместе взятых.

Наш проект свободный: можно использовать любую программу, скачав ее с сайта или написав самостоятельно. Самой важной является динамическая информация: какие диапазоны свободны для дальнейшего вычисления. В наших планах - создание полностью автоматического сервера (наподобие популярного GIMPS): вы выходите в Интернет, программа узнает об этом и отсылает на сервер информацию о проделанной работе и, если вычисления закончились, берет новую задачу. В начале года реальную помощь в проекте предложил итальянец Луиджи Морелли (Luigi Morelli). Он предоставил сервер, доменное имя и включился в создание автоматической базы данных.

Сводки

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

[i39458]


1 (обратно к тексту) - Число F24 имеет 5050445 десятичных знаков. Узнать другие технические подробности этого достижения и скачать код можно на www.perfsci.com/F24.
2 (обратно к тексту) - www.perfsci.com/prizes.html.
3 (обратно к тексту) - Профессор Крис Колдуэлл (Chris K. Caldwell) ведет список из 5 тыс. самых больших простых чисел всевозможных видов: www.utm.edu/research/primes/largest.html.
4 (обратно к тексту) - На сайте www.prothsearch.net можно найти программу и инструкции о том, как принять участие в проекте Proth по поиску гигантских простых чисел.
5 (обратно к тексту) - Крэйг Джонсон (Craig Johnston) высказал предположение, что не существует простых чисел вида S(n)=nn + 1, для n > 4. Вацлав Серпинский доказал (1958), что S(n) простое только тогда, когда число Ферма Fm, где m = j + 2j и n = 22j для j >= 0, простое (www.primepuzzles.net/conjectures/conj_016.htm), то есть достаточно доказать непростоту соответствующего числа Ферма.

Cводка найденного в докомпьютерную эпоху


Годы

Интервал лет

Найдено делителей

1640-1731

92

5 простых

1732-1854

123

2

1855-1900

46

7

1901-1952

52

7

Всего

313

16


Cводка найденного при помощи компьютеров (с 1953 г.)


Год

Найдено делителей

1953

2

1954

-

1955

-

1956

14

1957

6

1958

-

1959

-

1960

-

Всего

22

1961

-

1962

2

1963

11

1964

-

1965

-

1966

-

1967

-

1968

-

1969

-

1970

2

Всего

15

1971

-

1972

-

1973

-

1974

2

1975

-

1976

2

1977

4

1978

2

1979

13

1980

9

Всего

32

1981

3

1982

2

1983

2

1984

7

1985

2

1986

12

1987

5

1988

4

1989

-

1990

8

Всего

45

1991

12

1992

10

1993

10

1994

1

1995

8

1996

7

1997

4

1998

8

1999

9

2000

13

Всего

82

2001

8

Всего

8


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