Величайшие математические задачи - стр. 19

в степени log log n, где log – обозначение логарифма. Технически log log n может быть сколь угодно большим, поэтому данный алгоритм не относится к P-классу. Однако это не мешает ему быть пригодным к практическому использованию: если n – гуголплекс, т. е. 1 с 10^>100 нулями, то log log n равен примерно 230. Старая шутка гласит: «Доказано, что log log n стремится к бесконечности, но никто никогда не видел, как он это делает».

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

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

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