Лекция: На множители

Минимальные оценки предполагают бюджет $25000, алгоритм «квадратичное решето » и скорость техниче­ского прогресса 20 процентов в год. Средние оценки предполагают бюджет 25 миллионов долларов, алгоритм «решето общего поля чисел» и скорость технического прогресса 33 процента в год. Максимальные оценки пред­полагают бюджет 25 миллиардов долларов, алгоритм «решето общего поля чисел», работающий со скоростью

решета специального поля чисел и скорость технического прогресса 45 процентов в год

Всегда есть вероятность того, что успехи в разложении на множители будут поразительны и для меня, но я попытался учесть этот множитель в своих прогнозах. Но почему мне нужно верить? Я лишь продемонстрировал собственную глупость, занимаясь предсказаниями.

Табл. 7-8. Оптимистичные рекомендации Ривеста для длины клю-чей (в битах)

Вычисление с помощью ДНК

Это похоже на волшебство. В 1994 году Леонард Эдлман (Leonard M. Adleman) продемонстрировал метод решения задачи NP-полноты(см. раздел 11.2) в биохимической лаборатории, используя молекулы ДНК для представления возможных решений задачи [17]. Задача, решенная Эдлманом, была частным случаем задачи направленного гамильтонова пути: дана карта городов, соединенных однонаправленными дорогами, нужно на й-ти путь из города А в город Z, который проходит через каждый город на карте только один раз. Каждый город был представлен своей случайной цепочкой ДНК с 20 основаниями. С помощью обычных методов молекуляр­ной биологии Эдлман синтезировал 50 пикомолей (30 миллионов миллионов молекул) цепочки ДНК, представ­ляющей каждый город. Каждая дорога была представлена цепочкой ДНК с 20 основаниями, но эти цепочки выбирались не случайным образом: они умело выбирались так, чтобы «начало» цепочки ДНК, представляющей дорогу от города Р к городу К («Дорога РК») стремилась бы соединиться со цепочкой ДНК, представляющей город Р, а конец Дороги РК стремился бы соединиться с городом К.

Эдлман синтезировал 50 пикомолей ДНК, представляющих каждую дорогу, смешал их вместе с ДНК гор о-дами, представляющей города, и добавил фермент лигазу, которая связывает вместе концы молекул ДНК. Пра­вильно подобранная связь между цепочками ДНК для дорог и цепочками ДНК для городов приводит к тому, что лигаза соединяет цепочки ДНК для дорог вместе правильным образом. То есть, «Выход» дороги РК всегда будет соединен со «входом» какой-либо дороги, начинающейся в городе К, но никогда с «выходом» любой до­роги или со «входом» дороги, которая начинается не в городе К. После тщательно ограниченного времени реак­ции лигаза создала большое количество цепочек ДНК, представляющих возможные, но все равно случайные объединения путей карты.

В этом супе из случайных путей Эдлман может найти малейший след — может быть единственной молекулы — ДНК, которая является ответом задачи. Используя обычные методы молекулярной биологии, он удалил все цепочки ДНК, представлявшие слишком короткие или слишком длинные пути. (Число дорог в нужном пути должно равняться числу городов минус один.) Затем он удалил все цепочки ДНК, которые не проходили через город А, затем те, которые шли мимо города В, и так далее. Молекула ДНК, прошедшая через это сито, и пред­ставляет собой нужную последовательность дорог, являясь решением задачи направленного гамильтонова пути .

По определению частный случай задачи NP-полнотыможет быть преобразован за полиномиальное время к частному случаю любой другой задачи NP-полноты,и, следовательно, к задаче о направленном гамильтоновом пути. С семидесятых годов криптологи пытались использовать задачи NP-полнотыдля криптографии с откры­тыми ключами.

Хотя частный случай, решенный Эдлманом, весьма прост (семь городов на карте, простым наблюдением з а-дача моежт быть решена за несколько минут), это направление только начало развиваться, и не существует н и-каких препятствий для расширения данной методики на более сложные задачи. Таким образом, рассуждения о безопасности криптографических протоколов, основанных на задачах NP-полноты,рассуждения, которые до сих пор начинались словами, «Предположим, что у врага есть миллион процессоров, каждый из которых в ы-полняет миллион проверок каждую секунду», скоро, может быть, будут начинаться словами, «Предположим, у врага есть тысяча ферментных ванн, емкостью по 20000 литров каждая ».