= 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. Играть на таких условиях я согласен! – уж слишком мала эта вероятность.
Хотя у нас есть превосходные алгоритмы, как детерминированные, так и вероятностные, позволяющие находить простые числа для создания таких кодов, обычных алгоритмов для взлома этих кодов, по-видимому, не существует. А как насчет чего-нибудь не столь обычного?
Квантовые шорткаты
Одна из проблем, с которыми сталкиваются обычные компьютеры, когда пытаются решить задачу, подобную нахождению простых чисел для деления большого кодового числа, состоит в том, что им приходится проводить одну проверку, прежде чем они могут перейти к следующей. (Уточню для ясности, что в последующих рассуждениях я имею в виду только точное деление, без остатка.) Хорошо бы было разделить компьютер на части так, чтобы все они одновременно проводили разные проверки. Параллельная обработка – очень действенный способ ускорения работы. Взять, к примеру, строительство дома. В состязании на скорость строительства дома, проводившемся в Лос-Анджелесе, победила бригада из 200 строителей, работавших параллельно: они закончили свой дом за четыре часа. Разумеется, некоторые задачи необходимо выполнять последовательно. При строительстве многоэтажного дома или подземного гаража следующий этаж можно добавить, только когда будет построен предыдущий. Но перебор меньших чисел с проверкой того, делится ли на них большее, прекрасно можно производить параллельно. Каждая из таких проверок никак не зависит от результатов всех остальных.
Недостаток параллельной обработки данных состоит в том, что и она ограничивается физическими возможностями. Если разбить задачу на две, время, которое занимают проверки, уменьшится в два раза, но зато увеличится вдвое количество необходимой аппаратуры. По сути дела, такой подход не помогает находить простые делители большого числа.
Но что, если такую параллельную обработку можно было производить без непременного удвоения аппаратуры? Такая идея пришла в голову математику Питеру Шору, работавшему в 1990-х годах в компании Bell Labs: он понял, что для одновременной проверки нескольких вещей можно использовать довольно необычные методы информатики. Речь шла о странной физике квантового мира. В квантовой физике частица – например, электрон – может находиться, по сути дела, одновременно в двух местах, пока не будет произведено ее наблюдение. Эти два положения могут соответствовать числам 0 и 1. Это называется состоянием квантовой суперпозиции. Его преимущество в том, что здесь не требуется удвоения аппаратуры: речь по-прежнему идет об одном-единственном электроне. Но этот электрон хранит не один элемент информации, а два. Такая единица информации имеет особое название – кубит. В отличие от обычных компьютеров, в которых каждый бит должен находиться либо во включенном, либо в выключенном состоянии, то есть содержать либо 0, либо 1, кубит одновременно существует в параллельных квантовых мирах: в одном из них его значение равно 0, а в другом – 1.
Таким образом, было бы полезно создать целую последовательность таких кубитов. Например, если удастся объединить 64 кубита в состоянии квантовой суперпозиции, такой массив сможет одновременно представлять все числа от 0 до 264 – 1. Обычному компьютеру пришлось бы последовательно перебирать все эти числа, присваивая каждому биту значения, равные 0 или 1. Но квантовый компьютер может сделать это одновременно. В результате мой обычный компьютер, как электрон, как бы существует в нескольких параллельных вселенных сразу. В каждой из них эти 64 кубита представляют разные числа.
Тут-то и начинается самое интересное. В каждом из параллельных миров такой компьютер проверяет, является ли то число, которое он представляет, делителем кодового числа. Но как сделать так, чтобы квантовый компьютер сумел выбрать именно тот мир, в котором кодовое число успешно делится на число проверяемое? Именно этот вопрос решает блестящий прием Шора, который он встроил в свой алгоритм. Как только мы производим наблюдение квантовой суперпозиции, она должна принять решение и окончательно перейти в одно или другое состояние. По сути дела, она выбирает положение 0 или положение 1. Переход в то или иное положение определяется вероятностью.
Шор сумел создать такой алгоритм, который обеспечивает, что после проверки на делимость в каждой из параллельных вселенных квантовая суперпозиция с подавляющей вероятностью переходит в состояние того мира, в котором проверенное число оказалось делителем кодового числа. Все остальные миры, в которых результат проверки оказался отрицательным, настолько похожи друг на друга, что они взаимно уничтожаются. Остается только тот мир, в котором деление прошло успешно.
Представьте себе двенадцать векторов, исходящих из центра циферблата часов и направленных на его числа. Если все они равной длины, то при сложении взаимно уничтожатся, и останется лишь точка в центре циферблата. Но что произойдет, если один из них будет вдвое длиннее остальных? При сложении получится вектор, указывающий в этом направлении. По существу, то же самое происходит и при квантовом наблюдении проверок на делимость.
Хотя Шор написал свою программу еще в 1994 году, создание реального квантового компьютера, на котором этот алгоритм смог бы работать, казалось несбыточной мечтой. Одна из проблем квантовых состояний – это так называемая декогеренция. 64 кубита начинают наблюдать друг друга, и суперпозиция исчезает еще до выполнения вычислений. Это одна из причин, по которым, возможно, не существует кот Шредингера – квантовый мысленный эксперимент, в котором кот, пока его не наблюдают, может быть одновременно живым и мертвым. Разумеется, электрон может находиться в состоянии суперпозиции, но как все атомы, составляющие кота, могут одновременно быть в состояниях, в которых кот мертв и жив? Среди большого количества атомов начнутся взаимодействия, и декогеренция приведет к коллапсу суперпозиции.