Искусство мыслить рационально. Шорткаты в математике и в жизни

О задаче разложения чисел на простые множители писал в своем великом трактате по теории чисел под названием «Арифметические исследования» (Disquisitiones Arithmeticae, 1801) сам Гаусс: «То, что задача о том, как отличать составные числа от простых и разлагать первые на их простые сомножители, принадлежит к важнейшим задачам всей арифметики и привлекала внимание как математиков древности, так и математиков нашего времени, настолько хорошо известно, что было бы излишним тратить здесь на это много слов… Кроме того, и интересы самой науки как таковой обязывают приложить все усилия к решению этой столь изящной и знаменитой проблемы»[130].

Он, разумеется, не сознавал, насколько важной станет эта задача в эпоху интернета и электронной торговли. Пока что никто, в том числе и сам великий Гаусс, не придумал шортката к нахождению простых делителей крупных чисел. Количество простых чисел, которые нужно перебрать, чтобы расшифровать 200-значное число, так велико, что любая такая попытка будет абсолютно нецелесообразной. Мы предполагаем, что задача факторизации – выражения числа в виде произведения меньших чисел – может быть сложной по самой своей природе. Это один из нерешенных вопросов, над которыми работают сейчас математики. Сможем ли мы доказать, что шортката к нахождению простых чисел не существует?

Но погодите. Как же тогда расшифровывает сообщения сам веб-сайт? Дело в том, что он начинает выполнение этого алгоритма с выбора двух простых чисел приблизительно по 100 знаков каждое, а затем перемножает их для получения 200-значного кодового числа. Простые числа, позволяющие произвести это вычисление в обратном порядке, известны только веб-сайту, и никому другому.

Тем не менее нахождение простых чисел – это одна из задач, которые математики еще не решили. Секрет расположения простых чисел в численной вселенной, так называемая гипотеза Римана, также входит в число семи Задач тысячелетия. Но, хотя на самом деле математики не понимают, как распределены простые числа, у нас есть один интересный шорткат, помогающий находить большие простые числа для таких интернет-кодов. Он основывается на свойстве простых чисел, которое открыл великий французский математик XVII века Пьер де Ферма. Он доказал, что если p – простое число, то результат возведения любого числа n, меньшего p, в степень p делится на p с остатком, равным n. Например, 2⁵ = 32, а остаток от деления 32 на 5 равен 2.

Следовательно, если я хочу проверить, простое ли число, например, q, то обнаружение числа, меньшего q, для которого это правило не выполняется, означает, что q – число составное. Например, 2⁶ = 64, а остаток от деления 64 на 6 равен 4, а не 2. Значит, число 6 не может быть простым, потому что оно не проходит тест Ферма. Этот тест был бы не слишком полезным, если бы, скажем, существовало лишь одно число, меньшее q, для которого это условие не выполнялось бы. В таком случае, возможно, пришлось бы перебрать все числа, меньшие q, – а тогда с тем же успехом можно было бы прямо проверить число q на неделимость. Великое достоинство этого теста состоит в том, что если потенциальный кандидат в простые числа его проваливает, то проваливает он его с треском. При применении уловки Ферма оказывается, что более половины чисел, меньших q, свидетельствуют, что q – число не простое.

В этой бочке меда есть, однако, своя ложка дегтя. Бывают числа, которые ведут себя как простые, и никакие свидетели Ферма их не выдают, но простыми они не являются. Их называют псевдопростыми. Тем не менее в конце 1980-х годов два математика, Гари Миллер и Майкл Рабин, сумели усовершенствовать метод Ферма и разработать безошибочный тест на простоту чисел, работающий за полиномиальное время. Единственная оговорка состояла в том, что для этого им пришлось предположить, что существует возможность покорения одной чрезвычайно высокой вершины – гипотезы Римана (или ее обобщенного варианта).

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