Однако если я попрошу компьютер разложить на множители число 10199 + 1, в котором 200 цифр, то жужжать он будет долго, но результата так и не выдаст. Хотя, конечно, даже разложение числа из 100 цифр производит сильное впечатление. В чем тут секрет? В более эффективном по сравнению с последовательным перебором потенциальных простых делителей алгоритме поиска.
Мы сегодня знаем о первой из названных Гауссом задач (проверка числа на простоту) гораздо больше, чем знал он сам, и гораздо меньше, чем хотелось бы, о второй (разложение на простые множители). Здравый смысл говорит о том, что проверка на простоту намного проще разложения на простые множители. Как правило, это удивляет нематематиков, — ведь в школе учат проверять число на простоту тем же методом, что и искать его простые множители: перебором всех возможных делителей. Но, оказывается, существуют хитрые способы доказать простоту числа и без этого. Эти же методы позволяют доказать, что число составное, без нахождения каких бы то ни было его делителей. Достаточно показать, что это число не проходит тест на простоту.
Прапрадедушкой всех современных тестов на простоту может считаться теорема Ферма (чтобы не путать со знаменитой Великой теоремой, о которой речь пойдет в главе 7, ее иногда называют Малой теоремой Ферма). Эта теорема основана на модулярной арифметике, которую иногда называют еще «часовой арифметикой», поскольку числа в ней спирально накладываются друг на друга, как время на циферблате часов. Выберем число — для 12-часовых аналоговых часов это число 12 — и назовем его модулем. Теперь в любых арифметических вычислениях с неотрицательными целыми числами мы договоримся заменять любое число, кратное 12, нулем. К примеру, 5 × 5 = 25, но 24 — это дважды 12, поэтому вычтем из результата 24. Получим 5 × 5 = 1 по модулю 12. Модулярная арифметика очень красива, поскольку почти все обычные арифметические законы в ней тоже работают. Основная разница заключается в том, что мы не всегда можем разделить одно число на другое, даже если это не нуль. Модулярная арифметика полезна также тем, что обеспечивает удобный и аккуратный способ разбираться с вопросами делимости: какие числа делятся на те или иные модули без остатка и чему равен остаток, если это не так. Модулярную арифметику предложил Гаусс в «Арифметических исследованиях», и сегодня она широко используется не только в математике, но и в информатике, физике, инженерном деле.
Малая теорема Ферма утверждает, что если взять простой модуль p и любое число a, не кратное p, то степень (p − 1) числа a будет равна 1 по модулю p. Пусть, к примеру, p = 17 и a = 3. Тогда теорема предсказывает, что остаток от деления 316 на 17 будет равен 1. Проверим:
316 = 43 046 721 = 2 532 160 × 17 + 1.
Ни один человек, находящийся в своем уме, не захочет проводить подобные расчеты для, скажем, 100-значных простых чисел. К счастью, существует хитрый и быстрый способ сделать это. Смысл в том, что ответ не равен единице, если модуль, с которого мы начали, является составным числом. Так что теорема Ферма — надежная основа для эффективного теста, который обеспечивает необходимое условие простоты числа.
К несчастью, одного этого теста недостаточно. Известно, что его проходят и многие составные числа, известные как числа Кармайкла. Самое маленькое из них 561, и в 2003 г. Ред Элфорд, Эндрю Гранвиль и Карл Померанс доказали, к всеобщему изумлению, что таких чисел бесконечно много. Изумление математического сообщества вызвал тот факт, что авторам удалось найти доказательство; сам по себе результат особого удивления не вызвал. Фактически было доказано, что для каждого числа x существует по крайней мере x2/7 чисел Кармайкла, меньших или равных x, если x достаточно велико.
Однако более сложные варианты теоремы Ферма действительно можно превратить в тесты на простоту, такие как опубликованный в 1976 г. Гэри Миллером. К несчастью, доказательство достоверности теста Миллера опирается на одну из нерешенных великих математических задач — обобщенную гипотезу Римана (глава 9). В 1980 г. Майкл Рабин превратил тест Миллера в вероятностный, т. е. такой, который может иногда давать неверный ответ. Исключения, если они существуют, встречаются очень редко, но тем не менее доказать, что их нет, невозможно.
Наиболее эффективным детерминированным (т. е. дающим гарантированный результат) тестом на сегодняшний день является тест Адлемана — Померанса — Румели, названный в честь своих создателей — Леонарда Адлемана, Карла Померанса и Роберта Румели. В нем используются концепции теории чисел, куда более сложные, чем теорема Ферма, но примерно того же характера.
Я до сих пор помню письмо одного математика-любителя, предложившего вариант испытания делением. Давайте пробовать все возможные делители, предлагал этот энтузиаст, но начинать с корня квадратного из числа и двигаться, наоборот, вниз. Иногда этот метод действительно позволяет быстрее получить результат, чем при проверке делителей в обычном порядке, но с ростом чисел он, естественно, встречается с теми же проблемами, что и обычный метод. Если применить предложенный вариант к приведенному выше примеру, 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-значного числа приблизительно равняется 10n/2, а эта величина растет быстрее, чем любая фиксированная степень n. С таким типом роста, известным как экспоненциальный, по-настоящему трудно иметь дело, это страшный сон любого, кто занимается вычислениями.
