Окончание. Начало в #393, 394

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

Сегодня единственный известный способ поиска для m > 25 - это тривиальный перебор простых делителей, имеющих вид D = k•2ⁿ + 1, где n і m + 2. Операция деления F_m на D относительно простая, так как в ней используется модулярная арифметика. Чтобы доказать, что F_m делится на D, необходимо m раз произвести вычисления по рекуррентной формуле S_i = S²_i-1mod D, где S₀ = 2. Если S_m = -1, то делитель найден. Кроме того, можно ускорить вычисления в разы, если не искать делитель для конкретного F_m, а, взяв фиксированное n и нечетное k, выполнять вышеуказанные действия не более n - 2 раз, проверяя каждый раз условие S_i = -1. Другими словами, в процессе поиска выясняется следующее: может ли фиксированный делитель делить какое-нибудь число Ферма? ¹

На первый взгляд кажется, что все очень просто. Однако при вычислениях приходится сталкиваться с числами, превышающими разрядность компьютеров. В известной Библии для программистов Дональд Кнут ² собрал компьютерные алгоритмы почти на все случаи жизни, в том числе и для решения этих проблем. Примем S² = X•2ⁿ + Y (1), где числа X и Y получаются отсечением n бит двоичном представлении числа S². Если k меньше разрядности компьютера, то мы можем относительно легко найти два числа: q - частное и r - остаток, полученные при делении X на k. Тогда выражение (1) можно записать: S² = Y - q + 2ⁿr(mod k•2ⁿ + 1). Но самой длинной и сложной операцией является возведение в квадрат. Если это делать «классическим» методом, то его сложность пропорциональна n². Для больших чисел (больше тысячи знаков) это становится серьезной проблемой. Но математики нашли выход. В 1968 году Ф. Штрассен (V. Strassen) применил дискретное преобразование Фурье для умножения больших чисел. В этом случае необходимое количество вычислений пропорционально n•ln n. Этот продуктивный но сложный метод мы оставим за рамками статьи ³.

И все же модулярное деление F_m на D требует больших затрат времени. Чтобы ускорить перебор, мы должны брать «подходящие» (то есть простые) делители. Наша задача стала чуть легче. Но для дальнейшего повышения эффективности вычислений необходимо еще и быстро устранять большинство D.

Достаточно в начале вычислений найти много простых чисел p, тогда для каждого p находим такое k₀, чтобы соблюдалось тождество k₀2ⁿ == -1 (mod p), получая после преобразования -k₀ = ((p + 1) / 2)ⁿ (mod p). Тогда мы сможем применить известное со школы решето Эратосфена и отсеять все неподходящие k, как k₀, k₀ + p, k₀ + 2p, … Если взять 100000 простых чисел, то отбрасывается примерно 92% нечетных k.

Еще один прием оптимизации любой численной программы состоит в замене деления умножением на обратную величину (один раз вычисляем значение 1/x, а затем используем только операцию умножения) ⁴. Посмотрите внимательно: основная наша задача - делить числа, но во всем основном алгоритме программы Fermat нет ни одной команды деления.

Я до сих пор не могу в это поверить. 12 апреля произошло важное событие: немец Александр Круппа (Alexander Kruppa), используя программу MFAC Тони Форбса (Tony Forbes), неожиданно обнаружил делитель для числа F₃₁, равный 46931635677864055013377. Математическое сообщество буквально всколыхнулось и поздравило виновника торжества и друг друга. Ричард Крендалл тут же отметил, что этот делитель не мог быть обнаружен другими эффективными методами, например методами «p - 1» и «p + 1».

F₃₁ = 2^2147483648 + 1 - число особенное. Это последнее число Ферма, простота которого теоретически могла быть доказана на суперкомпьютерах хотя бы в ближайшие сто лет. Если бы оно оказалось простым, то был бы побит рекорд самого большого известного простого числа 2^6972593 - 1. Видимо, все же придется переосмыслить гипотезу о бесконечности простых чисел Ферма. Следующие подряд идущие числа Ферма, характер которых не известен, - F₃₃, F₃₄, F₃₅. Если не удастся обнаружить для них относительно небольшой делитель, то доказать их простоту человечество не сможет, вероятно, никогда. Начинается новая дьявольская гонка по устранению этих и других чисел из списка теоретически претендующих на роль самого большого известного простого числа.

Почему среди более чем полусотни человек, обнаруживших делители чисел Ферма, только трое россиян? Неужели русская школа программирования столь слаба или у нас компьютеры хуже? Вы не знаете, чем их занять? Так присоединяйтесь, еще очень многое надо сделать. Подробности на сайте www.fermatsearch.org.

P. S. Когда статья была уже готова, пришло сообщение о том, что еще один шаг сделал германский профессор Петер Гробстих (Peter Grobstich). Используя программу Fermat.exe, он нашел, что число F₃₄ делится на 482524552001•2⁹⁷ + 1. Гробстих весьма горд этим открытием и уже создал сайт, на котором рассказывает о своей работе (www.fh-nb.de/geo-inf/news/index.asp).

Кто следующий?

[i39559]

1 (обратно к тексту) - До сих пор в Интернете публикует свои работы некий Joe McLean‘s, который проделал гигантскую работу в поисках делителя для конкретного числа Ферма, но ему не суждено было найти новый делитель таким путем.
2 (обратно к тексту) - Дональд Кнут «Искусство программирования» тт. 1-3, ИД «Вильямс», 2000. Рекомендую приобрести эту книгу всем программистам, которые себя таковыми считают. О Д. Кнуте и его работе см. недавнюю тему номера в «КТ» #387.
3 (обратно к тексту) - Для интересующихся подробности на www.fftw.org.
4 (обратно к тексту) - Тут важно не забывать про округление результата. Операция деления - самое слабое место любого процессора - выполняется за 38-40 тактов. Для операции умножения необходимо менее 4 тактов.