Пара простых чисел в приведенном выше примере содержит лишь несколько цифр. Если мы возьмем простые числа, каждое из которых содержит сотни цифр, то время, которое потребуется компьютерной программе на простой перебор всех возможных вариантов — метод «грубой силы», как говорят криптографы, — будет больше, чем предполагаемое время существования Земли.
Простые числа повсеместно используются в нашей повседневной жизни, например, в кредитных картах и персональных компьютерах, поэтому постоянно существует потребность в новых простых числах (чем больше, тем лучше) для генерации секретных кодов. Таким образом, имеется спрос на простые числа, но контроль качества так же важен, как и их производство. Чтобы большому числу присвоить статус простого, его должна проверить специальная организация.
Шифр RSA был опубликован в 1978 г., но повсеместно начал использоваться в качестве метода шифрования лишь в конце 1990 гг. в связи с ростом сети интернет. Поиск больших простых чисел прежде требовал специального программного обеспечения, которое, как правило, можно было купить лишь в специализированных фирмах или в университетах, занимающихся такими исследованиями. Однако экспоненциальный рост вычислительных мощностей и появление более совершенных алгоритмов изменили рынок простых чисел и сделали их гораздо более доступными.
* * *
RSA-129
В апреле 1994 г. шифр RSA-129 потерпел полное фиаско. Он был построен на числе, содержащем 129 цифр, о чем объявили авторы этой системы шифрования, предложив желающим взломать его. Около 600 математиков с помощью 1600 добровольцев, найденных через интернет, работали над проблемой, и в конце концов им удалось разложить это число на множители. Однако было подсчитано, что если все компьютеры в мире будут работать параллельно, чтобы взломать код из 1024 цифр, им потребуется время, равное возрасту Вселенной (13,7 миллиарда лет). А теперь представьте себе, что в шифровании с открытым ключом используются числа, содержащие 128,1024 и даже 2048 цифр! Чем больше цифр использует система шифрования, тем устойчивее она к атакам, хотя это, конечно, замедляет процесс расшифровки.
* * *
Появление логарифмов позволило значительно сэкономить время при выполнении вычислений. Позже появились логарифмическая линейка и первые вычислительные машины, которые использовали вращающиеся цилиндры для выполнения операций сложения и умножения.
Тем не менее, именно компьютеры смогли делать вычисления, выходящие за пределы возможностей человеческого мозга. Машины могли даже имитировать дедуктивные рассуждения — одно из свойств математического мышления. В этот момент некоторые ученые почувствовали, что компьютеры достигли рубежа, к которому до сих пор ни одна машина не подходила. Был ли это правильный путь?
Экспоненциальный рост информационных технологий привел к изменению системы воззрений, сложившейся на протяжении веков. Начали появляться первые вычислительные алгоритмы, способные доказывать теоремы.
Противники компьютерных доказательств приводят два основных аргумента.
Во-первых, такие доказательства невозможно проверить, так как компьютерная программа содержит этапы, которые никакой математик никогда не сможет проконтролировать. Во-вторых, в процессе возможны ошибки из-за сбоев как в аппаратном, так и в программном обеспечении. В большинстве случаев эти ошибки случайны. Одним из способов предотвращения таких ошибок является использование различных программ на разных машинах (чтобы сравнить полученные результаты).
Но компьютеры могут работать только с кодами из единиц и нулей. Это накладывает некоторые ограничения, так как для чисел, которые не могут быть выражены в двоичной системе счисления, приходится использовать приближенные значения, что ведет к возможным ошибкам. В 1991 г. Дэвид Стаутмайер провел 18 экспериментов, доказав, что вычисления с помощью компьютерных программ могут дать неверные результаты.
Именно поэтому многие считают, что новые вычислительные методы исследований можно применять лишь в экспериментальной науке, а не в математике. Однако никто и не говорит, что в математике может быть использован лишь один метод.
Подсчитано, что у суперкомпьютера Cray на каждую тысячу часов работы приходится лишь одна ошибка.
«Традиционные» математические подходы тоже никогда не были свободны от ошибок. В ряде случаев неверные результаты считались правильными в течение многих
лет. Кроме того, в наши дни математика достигла такого высокого уровня разнообразия и сложности, что проверка доказательства теоремы может занять годы, или доказательство будет понятно в лучшем случае лишь нескольким специалистам.
Наконец, некоторые эксперты считают, что использование компьютера в качестве инструмента исследования и проверки теорем означает новое отношение к математике. Вполне разумно предположить, что гипотеза Римана в один прекрасный день может быть доказана с помощью компьютера. В любом случае, никто не ставит под сомнение правомерность того, что вычислительные методы используются для поиска и проверки простых чисел. В области вычислительной алгебры часто звучат такие термины, как детерминированный и вероятностный полиномиальные алгоритмы, которые совершенно непонятны для непосвященных. Хотя к нашей теме это не имеет прямого отношения, было бы полезно пояснить эти понятия.
Когда говорят о полиномиальном времени, имеют в виду время, необходимое компьютеру для выполнения некоего алгоритма. Предположим, что у нас есть входная переменная п. Если алгоритм использует полиномиальные выражения, например, n3 + 2n + 1, его называют полиномиальным алгоритмом (алгоритмом класса сложности Р). Если же выражение экспоненциальное, то говорят о неполиномиальном алгоритме (алгоритме класса сложности NP). В общих чертах идея состоит в том, что полиномиальные алгоритмы имеют приемлемое время работы, в отличие от неполиномиальных.
* * *
МАКСИМАЛЬНАЯ БЕЗОПАСНОСТЬ
Правительство США на своей территории и в Канаде допускает использование лишь определенных криптографических кодов. Также существует запрет на их продажу за пределами этих стран. Несанкционированный экспорт стандартов шифрования приравнивается к торговле оружием. Компании, производящие программы шифрования, хранят секретные коды в планшетах, оснащенных сложными устройствами безопасности. При взломе их содержимое превращается в бесформенную массу из-за контакта с кислородом. При попытке просканировать планшеты с помощью, например, рентгеновских лучей их содержимое преобразуется в нули.
* * *
Некоторые вычислительные задачи не могут быть решены с помощью детерминированного подхода — другими словами, с помощью процессов, выдающих уникальный и предполагаемый результат. Именно такими являются полиномиальные алгоритмы, работающие за полиномиальное время и выполняющие, например, операции сложения, умножения или решения систем уравнений. В большинстве случаев при использовании подходящих алгоритмов решение может быть найдено за разумное время. Задачи, которые могут быть решены таким образом, называются задачами класса сложности Р. С другой стороны, задачи класса сложности NP, для которых используются недетерминированные алгоритмы, решаются несколькими разными способами без гарантии получения одинакового результата.
Время, необходимое для решения такого рода проблем, намного больше чем для задач класса Р. Ясно, что любая проблема, которая допускает детерминированное решение за полиномиальное время, может быть также решена способом быстрой проверки. Другими словами, любая задача класса Р является также задачей класса NP. Однако на этом этапе нам следует уточнить понятие алгоритма.
Алгоритм можно сравнить с кулинарным рецептом. Он состоит из последовательности кристально ясных инструкций. Например, чтобы решить уравнение вида х — 2 = 8, можно использовать следующий алгоритм.
1. Отделить х (перенеся все члены, не содержащие х, в правую часть).
2. Выполнить сложение в правой части: 8 + 2 = 10.
3. Записать решение: х = 10.
Это задача класса Р, которую можно решить за полиномиальное время: она
очень проста и быстро решается.
Конечно, мы могли бы просто подставить значение, например х = 3, х = —2 и так далее, и времени на вычисления потребовалось бы меньше, так как единственное, что программа должна делать, — это подставлять значение вместо х и проверять равенство. Такой метод не является детерминированным, потому что всегда есть вероятность того, что решение будет неверным. (Мы предполагаем, что у нас есть определенные критерии для выбора диапазона возможных решений, например, условие, что все они должны находиться между 9 и 11.)
Можно поставить и обратный вопрос. Если у нас есть недетерминированный алгоритм, например, подстановки и проверки, можно ли гарантировать, что существует полиномиальный алгоритм, который позволяет решить задачу детерминировано? Другими словами, можем ли мы быть уверены в существовании алгоритма, решающего задачу за полиномиальное время?
Этот вопрос был поставлен независимо друг от друга Стивеном Куком и Леонидом Левиным в 1971 г.: если любая задача класса Р является также задачей класса NP, существуют ли задачи класса NP, которые не являются задачами класса Р?
Этот вопрос считается самой важной проблемой современной информатики и является одной из семи задач тысячелетия, за решение каждой из которых математическим институтом Клэя назначен приз в 1000 000 долларов США.
* * *
СЕМЬ ЗАДАЧ ТЫСЯЧЕЛЕТИЯ
Математический институт Клэя — частная некоммерческая организация, основанная Лэндоном Клэем, мультимиллионером и бизнесменом из Бостона. Цель института заключается в развитии и распространении математических знаний.
25 мая 2000 г. институт опубликовал список задач тысячелетия — наиболее сложных проблем математики XX в., за решение которых в общей сложности будет выплачено семь миллионов долларов. Задачи можно решать по одной; за решение каждой будет выдаваться приз в миллион долларов (это больше, чем Нобелевская премия). Институт не накладывает никаких ограничений на сроки решения и возраст кандидатов. Вот эти семь задач.