.

время вычислений росло экспоненциально. Однако в 1983 г. был найден алгоритм, очень соблазнительно лежащий на ничьей земле вблизи P-территории: это уже упоминавшийся тест Адлемана – Померанса – Румели. Его улучшенная версия, разработанная Генри Коэном и Хендриком Ленстрой, имела время вычисления n в степени log log n, где log – обозначение логарифма. Технически log log n может быть сколь угодно большим, поэтому данный алгоритм не относится к P-классу. Однако это не мешает ему быть пригодным к практическому использованию: если n – гуголплекс, т. е. 1 с 10¹⁰⁰ нулями, то log log n равен примерно 230. Старая шутка гласит: «Доказано, что log log n стремится к бесконечности, но никто никогда не видел, как он это делает».

      Первый тест на простоту, принадлежащий к P-классу, открыли в 2002 г. Маниндра Агравал и его студенты-дипломники Нирадж Каял и Нитин Саксена. В Примечаниях можно прочитать об этом немного подробнее{2}. Они придумали алгоритм и доказали, что время его выполнения растет пропорционально не более чем n¹²; очень скоро эта величина была уменьшена до n^7,5. Однако, несмотря на то что их алгоритм относится к P-классу и, соответственно, считается «эффективным», его преимущества не проявляются до тех пор, пока n не становится очень и очень большим. По идее этот алгоритм должен побить тест Адлемана – Померанса – Румели, когда число знаков в n приблизится к 10¹⁰⁰⁰. Но такое большое число невозможно разместить не только в память компьютера, но и вообще в известной Вселенной. Зато теперь мы точно знаем, что алгоритмы P-класса для проверки простоты числа существуют. Ясно, что поиск лучших алгоритмов в этой категории – дело стоящее. Ленстра и Померанс снизили степень с 7,5 до 6. Если еще некоторые предположения о свойствах простых чисел подтвердятся, степень можно будет снизить до 3, что приблизит нас к практическому применению подобных алгоритмов.

      Но самое интересное в алгоритме Агравала – Каяла – Саксены – не результат, а метод. Он прост – по крайней мере для математиков – и отличается новизной. В основе его лежит вариант теоремы Ферма, но, вместо того чтобы работать с числами, команда Агравала использовала многочлены. Многочлен, или полином, – это комбинация степеней переменной x, такая, к примеру, как 5x³ + 4x − 1. Многочлены можно складывать, вычитать и перемножать, и обычные алгебраические законы на них тоже распространяются. В главе 3 мы поговорим о многочленах подробнее.

      По-настоящему великолепная идея: расширить пространство дискурса и перенести проблему в новую область. Это тот самый случай, когда идея проста настолько, что нужно быть гением, чтобы разглядеть ее. Первый намек на нее проскользнул в статье Агравала и его научного консультанта Сомената Бисваса: авторы предложили вероятностный тест на простоту, основанный на аналоге теоремы Ферма в мире полиномов. Агравал был убежден, что вероятностный компонент этого метода может быть устранен. В 2001 г. его

2

Алгоритм Агравала – Каяла – Саксены выглядит так:

• Если n представляет собой точную степень меньшего числа, выдаем СОСТАВНОЕ.

• Находим наименьшее r, такое, что наименьшая степень r, равная 1 по модулю n, больше или равна (log n)².

• Если какое-либо число, меньшее или равное r, имеет общий делитель с n, выдаем СОСТАВНОЕ.

• Если n меньше или равно r, выдаем ПРОСТОЕ.

• Для всех целых чисел a от 1 до определенного предела проверяем, совпадает ли многочлен (x + a)ⁿ с многочленом xⁿ + a по модулю n и по модулю x^r − 1. Если в обоих случаях ответ положительный, выдаем СОСТАВНОЕ.

• Выдаем ПРОСТОЕ.