Онлайн чтение книги Величайшие математические задачи The greatest mathematical problems
2. Территория простых чисел. Проблема Гольдбаха

Некоторые великие задачи встречаются и в начальном курсе математики, хотя мы этого не замечаем. Вскоре после того, как ребенок осваивает умножение, он знакомится с концепцией простого числа. Известно, что некоторые числа могут быть получены при перемножении двух меньших чисел, к примеру: 6 = 2 × 3. Другие, такие как 5, невозможно разложить подобным образом на сомножители. Максимум, что можно сделать, это записать 5 = 1 × 5, но в этом выражении нет двух меньших чисел. Числа, которые можно разбить на сомножители, называют составными, а те, что разложить невозможно, – простыми. Простые числа кажутся такой несложной темой! Если вы уже умеете перемножать натуральные числа, то способны разобраться и в том, что представляет собой простое число. Простые числа – первичные строительные кирпичики для всех натуральных чисел, и обнаружить их можно в самых разных разделах математики. Но в них есть тайна, и, на первый взгляд, они раскиданы среди положительных целых чисел почти случайным образом. Нет никаких сомнений: простые числа – настоящая загадка. Возможно, это естественное следствие их определения – ведь определяются они не через какое-либо присущее им свойство, а напротив – через свойство, которое у них отсутствует. С другой стороны, для математики это фундаментальное понятие, поэтому мы не можем просто так в ужасе поднять руки и сдаться. Нам необходимо с ними освоиться и каким-то образом вызнать их потаенные секреты.

Некоторые свойства простых чисел очевидны. За исключением самого маленького из них, двойки, все они нечетные. Сумма цифр простого числа, за исключением тройки, не может быть кратна трем. Они, за исключением пятерки, не могут заканчиваться на цифру 5. Если же число не подпадает под эти правила – и под несколько других, более тонких, – то невозможно посмотреть на него и сразу сказать, простое это число или нет. Да, существуют формулы для простых чисел, но это в значительной степени обман. Эти формулы не дают никакой полезной новой информации о простых числах; это просто хитрый способ зашифровать определение «простоты» в виде формулы. Простые числа – как люди: каждое из них – личность, и они не подчиняются общим правилам.

За тысячелетия математики сумели постепенно расширить свои знания о простых числах. Время от времени и сегодня решаются новые серьезные проблемы, с ними связанные. Однако многие вопросы по-прежнему остаются нерешенными. Некоторые из них фундаментальны и легко формулируются, другие понятны немногим. В этой главе говорится о том, что мы знаем и чего не знаем об этих раздражающих своей неприступностью, но все же фундаментальных числах. Начинается она с установления некоторых базовых понятий: в частности, концепции разложения на простые множители – как представить заданное число в виде произведения простых чисел. Даже этот знакомый процесс заводит нас на глубину сразу же, как только мы начинаем задавать вопросы о по-настоящему эффективных методах поиска простых множителей конкретного числа. Как ни удивительно, определить, является ли данное число простым, относительно несложно, но если число составное, то отыскать его простые множители часто намного труднее.

Разобравшись в основах, перейдем к самой известной из нерешенных задач, связанных с простыми числами, – к проблеме Гольдбаха, которой уже 250 лет. В последнее время в работе над ней достигнут колоссальный прогресс, но полностью она пока не решена. А несколько других задач представят нам примеры того, что еще предстоит сделать в этой важной, но трудно поддающейся исследованию области математики.

Простые числа и разложение на множители знакомы нам из школьного курса арифметики, однако большинство интересных свойств простых чисел на этом уровне не рассматривают и никаких доказательств не представляют. Тому есть веские причины: доказательства даже самых очевидных, на первый взгляд, свойств удивительно сложны. Вместо этого школьников учат некоторым простым методикам работы с простыми числами, акцентируя внимание на вычислениях, где цифры относительно невелики. В результате наши первые впечатления от встречи с простыми числами, как правило, обманчивы.

Древние греки были знакомы с некоторыми базовыми свойствами простых чисел и знали, как их доказать. Простые числа и сомножители – основная тема Книги VII евклидовых «Начал», классического труда, посвященного геометрии. В этой книге имеется, в частности, геометрическое представление арифметических действий – деления и умножения. Греки предпочитали работать не с числами как таковыми, а с длинами линий (отрезков), но их результаты несложно переформулировать на языке чисел. Так, Предложение 16 Книги VII доказывает, что при перемножении двух чисел результат не зависит от того, в каком порядке берутся эти числа. Иными словами, ab = ba, фундаментальный закон алгебры.

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

Затем берем все простые числа, которые присутствуют в обоих разложениях, в наибольшей общей степени; получаем 32 × 5. Перемножаем, получаем 45. Это и есть наибольший общий делитель. Из этой процедуры создается впечатление, что без разложения на простые множители невозможно найти наибольший общий делитель. На самом деле с точки зрения логики все наоборот. Предложение 2 Книги VII «Начал» представляет метод поиска наибольшего общего делителя двух натуральных чисел без разложения их на простые множители. Метод состоит в последовательном вычитании меньшего числа из большего, а затем остатка из меньшего числа и т. д. до тех пор, пока есть остаток. Для тех же чисел 135 и 630 – это достаточно типичный случай для небольших чисел – процесс выглядит так. Вычитаем 135 из 630 столько раз, сколько сможем:

630 − 135 = 495;

495 − 135 = 360;

360 − 135 = 225;

225 − 135 = 90.

Поскольку 90 < 135, переходим к той же процедуре с участием чисел 90 и 135:

135 − 90 = 45.

Поскольку 45 < 90, продолжаем то же с числами 45 и 90:

90 − 45 = 45;

45 − 45 = 0.

Таким образом, наибольший общий делитель чисел 135 и 630 равен 45.

Эта процедура работает потому, что на каждой стадии происходит замена первоначальной пары чисел более простой парой (одно из чисел уменьшается), которая тем не менее имеет тот же наибольший общий делитель. В конце концов, одно из чисел делится на второе нацело, без остатка, и процесс поиска на этом завершается. В наше время подробное описание вычислительного метода, при помощи которого можно гарантированно найти ответ той или иной задачи, называют алгоритмом. Поэтому и процедура из «Начал» Евклида известна сегодня как евклидов алгоритм. Логически эта процедура первична по отношению к процедуре разложения на простые множители. В самом деле, Евклид использует ее для доказательства основных свойств простых делителей. В современных университетских курсах математики алгоритм Евклида используется с той же целью.

Описанная процедура целиком опирается на евклидово Предложение 30 и была бы невозможна без него. В современных терминах речь в нем идет о том, что если произведение двух чисел – то, что мы получаем при их перемножении – делится на некое простое число, то на это же число должен делиться один из сомножителей. Предложение 32 заключается в том, что любое число либо само является простым, либо имеет простой делитель. Объединив оба утверждения, несложно сделать вывод, что любое число есть результат перемножения простых множителей и что их набор единственный, если не брать во внимание порядок записи. К примеру,

и т. д., но единственный реальный способ получить 60 состоит в том, чтобы взять множители из первого разложения и переставить их местами. Не существует, к примеру, разложения, в котором 60 = 7 × что-нибудь. Существование какого-нибудь разложения следует из Предложения 32. Если число простое – стоп. Если нет, находим простой делитель, делим на него, получая меньшее число, и повторяем процедуру. Уникальность набора делителей следует из Предложения 30. Так, если бы разложение 60 = 7 × что-нибудь существовало, то одно из чисел 2, 3 и 5 должно было бы тоже делиться на 7, но этого не происходит.

Здесь я должен прояснить один небольшой, но важный момент: исключительный статус числа 1. Согласно приведенному выше определению, оно простое: если мы попытаемся разбить его на множители, максимум, что мы получим, будет 1 = 1 × 1, где нет меньших чисел. Однако позже, с развитием теории, такая интерпретация вызывает проблемы, поэтому в последние век-два математики добавили в определение простого числа дополнительное ограничение. Число 1 настолько отличается от всех остальных чисел, что его следует рассматривать как исключение, – это не простое число, но и не составное. Это третья разновидность числа – единица. Одна из причин, по которым мы называем 1 особым случаем, а не относим ее к настоящим простым числам, заключается в том, что если мы согласимся с простотой единицы, то единственность набора множителей нарушится. Вообще-то 1 × 1 = 1 – уже нарушение, а уж 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 = 1 ни в какие ворота не лезет. Можно было бы изменить определение единственности и сказать «единственный, без учета дополнительных единичных множителей», но это был бы всего лишь другой способ признать, что 1 – число особое.

Много позже, в Предложении 20 Книги IX, Евклид доказывает еще один ключевой факт: «Простых чисел существует больше, чем их насчитывается в любом множестве простых чисел». Иными словами, множество простых чисел бесконечно. Это чудесная теорема и изящное доказательство, но ее появление вызвало множество проблем. Если простые числа уходят в бесконечность, но, судя по всему, расположены без всякой системы, то как можно сказать, на что они похожи?

Мы вынуждены обратиться к этому вопросу потому, что не можем оставить в стороне простые числа – очень существенную деталь математического ландшафта. Особенно часто они встречаются (и особенно полезны) в теории чисел – разделе математики, изучающем свойства целых чисел. Звучит, может быть, достаточно элементарно, но на самом деле теория чисел – один из самых глубоких и сложных разделов математики. Позже мы увидим тому множество свидетельств. В 1801 г. Гаусс, ведущий специалист того времени по теории чисел (а также, по мнению некоторых ученых, один из ведущих математиков всех времен, а может быть, и величайший из них), написал продвинутый учебник по этой теории – «Арифметические исследования» ( Disquisitiones Arithmeticae ). В нем среди множества сложных тем Гаусс указал, что не следует терять из виду два весьма фундаментальных вопроса: «Известно, что задача отличения простых чисел от составных и разложения последних на простые множители является одной из важнейших и полезнейших в арифметике».

В школе, как правило, учат ровно одному способу поиска простых делителей числа. Заключается он в том, чтобы пробовать по очереди все потенциальные делители, пока не найдется такой, на который число разделится нацело. Если вы не нашли ни одного делителя к тому моменту, как добрались до корня квадратного из первоначального числа – точнее, до наибольшего целого числа, меньшего или равного этому корню, – то число это простое. В противном случае вы найдете множитель, разделите на него и продолжите с новым числом с того же места. Эффективнее всего пробовать только простые делители, но для этого необходим список простых чисел. Поиск останавливается на корне квадратном из числа, потому что наименьший делитель любого составного числа не превосходит корень квадратный из этого числа. Однако для больших чисел эта процедура безнадежно неэффективна. К примеру, если взять число

то на простые множители оно раскладывается следующим образом:

и, чтобы добраться до меньшего из двух множителей, вам придется опробовать каждое из первых 624 401 249 простых чисел. Конечно, при помощи компьютера это несложно сделать, но если взять для начала число из 100 цифр, которое – так уж случилось – раскладывается на два множителя по 50 цифр в каждом, то систематический перебор последовательных простых чисел продлится до конца Вселенной и вряд ли успеет дать результат.

Нет, вообще-то современные компьютеры, как правило, умеют раскладывать числа из 100 цифр на простые множители. Моему компу требуется меньше секунды, чтобы найти простые множители числа 10⁹⁹ + 1 (выглядит это число как 1000 … 001 с 98 нулями). Это число – результат перемножения 13 простых чисел (одно из них повторяется дважды), наименьшее из которых – 7, а наибольшее – 141 122 524 877 886 182 282 233 539 317 796 144 938 305 111 168 717.

Однако если я попрошу компьютер разложить на множители число 10¹⁹⁹ + 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. Тогда теорема предсказывает, что остаток от деления 3¹⁶ на 17 будет равен 1. Проверим:

Ни один человек, находящийся в своем уме, не захочет проводить подобные расчеты для, скажем, 100-значных простых чисел. К счастью, существует хитрый и быстрый способ сделать это. Смысл в том, что ответ не равен единице, если модуль, с которого мы начали, является составным числом. Так что теорема Ферма – надежная основа для эффективного теста, который обеспечивает необходимое условие простоты числа.

К несчастью, одного этого теста недостаточно. Известно, что его проходят и многие составные числа, известные как числа Кармайкла. Самое маленькое из них 561, и в 2003 г. Ред Элфорд, Эндрю Гранвиль и Карл Померанс доказали, к всеобщему изумлению, что таких чисел бесконечно много. Изумление математического сообщества вызвал тот факт, что авторам удалось найти доказательство; сам по себе результат особого удивления не вызвал. Фактически было доказано, что для каждого числа x существует по крайней мере x ^2/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 -значного числа приблизительно равняется 10 ^{n /2}, а эта величина растет быстрее, чем любая фиксированная степень  n . С таким типом роста, известным как экспоненциальный, по-настоящему трудно иметь дело, это страшный сон любого, кто занимается вычислениями.

До 1980-х гг. у всех известных алгоритмов проверки на простоту, за исключением вероятностных или тех, надежность которых оставалась недоказанной, время вычислений росло экспоненциально. Однако в 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 представляет собой точную степень меньшего числа, выдаем СОСТАВНОЕ. • Находим наименьшее r , такое, что наименьшая степень r , равная 1 по модулю n, больше или равна (log  n )². • Если какое-либо число, меньшее или равное r , имеет общий делитель с  n , выдаем СОСТАВНОЕ. • Если n меньше или равно r , выдаем ПРОСТОЕ. • Для всех целых чисел a  от 1 до определенного предела проверяем, совпадает ли многочлен ( x + a ) ⁿ с многочленом x ⁿ + a по модулю n и по модулю x ^r − 1. Если в обоих случаях ответ положительный, выдаем СОСТАВНОЕ. • Выдаем ПРОСТОЕ.. Они придумали алгоритм и доказали, что время его выполнения растет пропорционально не более чем n ¹²; очень скоро эта величина была уменьшена до  n ^7,5. Однако, несмотря на то что их алгоритм относится к P-классу и, соответственно, считается «эффективным», его преимущества не проявляются до тех пор, пока n не становится очень и очень большим. По идее этот алгоритм должен побить тест Адлемана – Померанса – Румели, когда число знаков в  n приблизится к 10¹⁰⁰⁰. Но такое большое число невозможно разместить не только в память компьютера, но и вообще в известной Вселенной. Зато теперь мы точно знаем, что алгоритмы P-класса для проверки простоты числа существуют. Ясно, что поиск лучших алгоритмов в этой категории – дело ст о ящее. Ленстра и Померанс снизили степень с 7,5 до 6. Если еще некоторые предположения о свойствах простых чисел подтвердятся, степень можно будет снизить до 3, что приблизит нас к практическому применению подобных алгоритмов.

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

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

В те времена, когда теория чисел пребывала в своей башне из слоновой кости, вся эта история прошла бы незамеченной и никак не повлияла бы на жизнь остального мира. Но в последние 20 лет простые числа приобрели огромный вес в криптографии – науке о шифрах. Шифры важны не только для военных, у коммерческих компаний тоже хватает секретов. Сегодня, в век Интернета, секреты есть у каждого из нас: мы не хотим, чтобы преступники получили доступ к нашим банковским счетам и номерам кредитных карт. Мало того, все чаще в преступных целях используются и другие личные данные, так что хотелось бы уберечь их все, вплоть до клички домашней кошки. Но Интернет невероятно удобен при оплате счетов, страховании машин и заказе всего, что необходимо для поездки на отдых, и всем нам приходится мириться с риском того, что ценная частная информация попадет не в те руки.

Производители компьютеров и интернет-провайдеры пытаются снизить этот риск, предлагая пользователям различные системы шифрования. Надо сказать, что внедрение компьютеров изменило как саму криптографию, так и криптоанализ – искусство взлома шифров. В настоящее время разработано множество новых шифров. Один из самых известных шифров, который в 1978 г. придумали Рональд Ривест, Ади Шамир и Леонард Адлеман, основан на использовании простых чисел. Больших простых чисел, примерно 100-значных. Система Ривеста – Шамира – Адлемана (известная как RSA) используется во многих компьютерных операционных системах, встроена в основные протоколы безопасного интернет-соединения, ею широко пользуются правительства, корпорации и университеты. Конечно, не каждое новое открытие, имеющее отношение к простым числам, может повлиять на безопасность вашего банковского счета, но это добавляет теме интереса. Как только удается выяснить что-то новое, что помогает связать простые числа и компьютерные вычисления, это привлекает повышенное внимание. Так случилось и с тестом Агравала – Каяла – Саксены, хотя при всей своей математической элегантности и важности непосредственного практического значения он не имеет.

Тем не менее он позволил немного под другим углом рассмотреть общий вопрос криптографии по Ривесту – Шамиру – Адлеману, и результат вызывает некоторые опасения. До сих пор не существует ни одного алгоритма P-класса для решения второй из названных Гауссом задач – разложения на простые множители. Большинство специалистов сходятся во мнении, что такого алгоритма не существует, но в последнее время их уверенность несколько поколебалась. Поскольку где-то за кулисами, совсем рядом, могут скрываться и другие открытия, подобные тесту Агравала – Каяла – Саксены и основанные на таких же простых идеях, как полиномиальная версия теоремы Ферма (и не важно, что пока о них никто даже не подозревает), может оказаться, что системы шифрования, основанные на разложении числа на простые множители, не настолько надежны, как нам хочется верить. Так что пока не стоит раскрывать в Интернете кличку вашей кошки!

Даже элементарная математика простых чисел ведет к выдвижению более сложных концепций. Евклид доказал, что простые числа уходят в бесконечность, так что невозможно просто перечислить их все и успокоиться. Мы не можем также дать простую и практичную алгебраическую формулу для вычисления всех простых чисел подряд, примерно так, как по формуле x ² вычисляются квадраты чисел. (Простые формулы существуют, но они «мошенничают», встраивая в формулу сами простые числа под разными личинами, и в результате не сообщают нам ничего нового{3}Примером того, что я имею в виду, может служить формула, где квадратные скобки обозначают наибольшее целое число, меньшее или равное их содержимому. В 1947 г. У. Миллс доказал, что существует действительная константа A, такая, что для любого n вычисленное по этой формуле значение будет простым. Если считать гипотезу Римана верной, то минимальное значение A , удовлетворяющее условию, равно приблизительно 1,306. Однако эта константа определяется при помощи подходящей последовательности простых чисел, а формула – всего лишь символьный способ записи этой последовательности. Подобные формулы, включая некоторые из тех, что представляют все простые числа, представлены также на сайтах: http://mathworld.wolfram.com/PrimeFormulas.html; http://en.wikipedia.org/wiki/Formula_for_primes..) Пытаясь познать природу этих неуловимых и странных чисел, мы экспериментируем, ищем в них признаки структурированности и пытаемся доказать, что найденные нами закономерности присутствуют во всех простых числах, какими бы большими они ни были. Можно, к примеру, задаться вопросом о том, как простые числа распределены среди всех целых чисел. Таблицы простых чисел позволяют предположить, что чем дальше, тем таких чисел становится меньше. В табл. 1 показано, сколько простых чисел содержится в разных диапазонах на 1000 последовательных целых чисел.