Наиболее эффективным детерминированным (т. е. дающим гарантированный результат) тестом на сегодняшний день является тест Адлемана — Померанса — Румели, названный в честь своих создателей — Леонарда Адлемана, Карла Померанса и Роберта Румели. В нем используются концепции теории чисел, куда более сложные, чем теорема Ферма, но примерно того же характера.

Я до сих пор помню письмо одного математика-любителя, предложившего вариант испытания делением. Давайте пробовать все возможные делители, предлагал этот энтузиаст, но начинать с корня квадратного из числа и двигаться, наоборот, вниз. Иногда этот метод действительно позволяет быстрее получить результат, чем при проверке делителей в обычном порядке, но с ростом чисел он, естественно, встречается с теми же проблемами, что и обычный метод. Если применить предложенный вариант к приведенному выше примеру, 22-значному числу 1 080 913 321 843 836 712 253, то квадратный корень из него равен примерно 32 875 725 419. Вам придется перепробовать 794 582 971 простой делитель, прежде чем вы доберетесь до нужного. Это хуже, чем искать его обычным путем.

В 1956 г. знаменитый логик Курт Гедель в письме к Джону фон Нейману почти буквально повторил мольбу Гаусса. Он спрашивал, можно ли улучшить метод пробного деления, и если можно, то насколько. Фон Нейман не стал заниматься этим вопросом, но позже другие математики ответили Геделю, открыв практические методы нахождения простых чисел длиной до 100 знаков, а иногда даже больше. Эти методы, самый известный из которых называется методом квадратичного решета, появились около 1980 г. Однако почти все они либо вероятностны, либо неэффективны в следующем смысле.

Как увеличивается компьютерное время, необходимое для вычислений, с ростом объема исходных данных? При тестировании на простоту исходные данные — это не само число, а число знаков в нем. Ключевое различие в этом случае проводится между двумя группами алгоритмов — алгоритмами, принадлежащими и не принадлежащими к классу P. Если время работы алгоритма растет как некая фиксированная степень от размера исходных данных, то алгоритм принадлежит к классу P; в противном случае — не принадлежит. Грубо говоря, алгоритмы класса P полезны, тогда как те, что не принадлежат к этому классу, непрактичны. Существует, однако, промежуточная полоса своеобразной ничьей земли, где в ход идут другие соображения. Класс P получил название от понятия «полиномиальное время» — именно так замысловато математики говорят о постоянных степенях. Мы еще вернемся к теме эффективных алгоритмов позже, в главе 11.

По стандартам класса P метод пробного деления работает из рук вон плохо. На школьном уровне, где для проверки предлагаются двух— или трехзначные числа, с ним все в порядке, но при работе со 100-значными числами он абсолютно безнадежен. В общем, пробное деление никак не укладывается в P-класс. Если быть точным, то время выполнения этого алгоритма для любого n-значного числа приблизительно равняется 10^n/2, а эта величина растет быстрее, чем любая фиксированная степень n. С таким типом роста, известным как экспоненциальный, по-настоящему трудно иметь дело, это страшный сон любого, кто занимается вычислениями.

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