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

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

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

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

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

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

362128936829849024182024971631805407255830459520
272960891514314523640507570656742232821636569307•211 + 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

Сводки

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

[i39458]