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

Подозрительная простота

Коды, которые защищают сегодня наши кредитные карты, «летающие» по интернету, используют математические задачи, к решению которых, как мы считаем, в принципе не может быть шорткатов. В основе одного из таких шифров, который называется RSA[129], лежит загадочная категория чисел – простые числа. Каждый веб-сайт выбирает два секретных простых числа длиной порядка 100 знаков и перемножает их. Получившееся число, имеющее в длину около 200 знаков, можно опубликовать на сайте. Это кодовое число данного сайта. Когда я посещаю этот сайт, мой компьютер получает это 200-значное число, которое используется затем в математических операциях с моей кредитной картой. Зашифрованное таким образом число можно пересылать по интернету. Оно надежно защищено, так как для его расшифровки хакеру нужно было бы найти два простых числа, произведение которых дает 200-значное кодовое число веб-сайта. Такой шифр считается надежным, потому что эта задача, по-видимому, относится к категории задач об иголках в стогах сена. Математикам известен лишь один способ подбора таких простых чисел: перебирать эти числа одно за другим, надеясь случайно набрести на иголку, то есть на число, на которое кодовое число сайта делится без остатка.

О задаче разложения чисел на простые множители писал в своем великом трактате по теории чисел под названием «Арифметические исследования» (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-х годов два математика, Гари Миллер и Майкл Рабин, сумели усовершенствовать метод Ферма и разработать безошибочный тест на простоту чисел, работающий за полиномиальное время. Единственная оговорка состояла в том, что для этого им пришлось предположить, что существует возможность покорения одной чрезвычайно высокой вершины – гипотезы Римана (или ее обобщенного варианта).