Искусство мыслить рационально. Шорткаты в математике и в жизни - Маркус Дю Сотой

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

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

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

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

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

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

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

Однако никогда не следует терять надежды, что может найтись хитрая тропа, по которой гору можно обойти. В 2002 году математическое сообщество потрясла новость, что три индийских математика, Маниндра Агравал, Нирадж Каял и Нитин Саксена, работающие в Технологическом институте Канпура, открыли способ тестировать простоту чисел за полиномиальное время, не требующий перехода через гору Римана. Замечательно то обстоятельство, что двое из авторов этого открытия были студентами, писавшими дипломы под руководством Агравала. Даже сам Агравал, старший член этой группы, не был известен большинству математического сообщества. Многим это напомнило об истории великого Рамануджана, который внезапно ворвался на математическую сцену в начале XX века, написав о своих открытиях кембриджскому математику Г. Х. Харди.

Хотя открытие этой группы дало нам тест на простоту чисел, работающий за полиномиальное время и не требующий возможности перехода через гору Римана, в реальной жизни этот алгоритм был не слишком практичным. Как я уже говорил, важно знать степень используемого полинома. Если речь идет о квадратном полиноме, алгоритм работает быстро. Однако исходный алгоритм, который предложили Агравал, Каял и Саксена, имел полиномиальную сложность 12-й степени. Это число уменьшили до 6 американский математик Карл Померанс и голландский математик Хендрик Ленстр, но, как я уже объяснял, хотя с математической точки зрения такое решение и считается шорткатом, на практике оно очень быстро замедляется. По мере роста чисел, которые мы тестируем, работа алгоритма с полиномиальной сложностью шестой степени занимает существенно больше времени.

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

Вспомним, что если некое число не простое и не псевдопростое, то половина чисел, меньших его, не пройдут тест Ферма. Но что, если нам так сильно не повезет, что мы проверим именно те числа, которые пройдут этот тест? Казалось бы, чтобы найти свидетеля составного характера числа, необходимо проверить половину меньших его чисел. Но какова вероятность не попасть на такого свидетеля? Предположим, мы проверили 100 чисел и не нашли ни одного свидетеля. Это означает одно из двух: либо наше число простое или псевдопростое, либо нам действительно не попалось ни одного свидетеля, но вероятность такого события составляет 1 к 2100. Играть на таких условиях я согласен! – уж слишком мала эта вероятность.