Традиционно для решения математических (в том числе криптоаналитических) задач используются компьютеры, реализованные в виде электронных устройств, универсальных (программируемых) или специализированных, сконструированных для решения конкретной задачи. Такие компьютеры могут различаться разрядностью, объемом памяти, тактовой частотой, конфигурацией. Все эти компьютеры как вычислительные модели полиноминально эквивалентны (предполагается, что объем памяти достаточен для реализации данного вычислительного алгоритма). Это означает, что если задача может быть решена за п шагов на одной вычислительной модели, то она может быть решена за п шагов на другой вычислительной модели.
Поэтому множества вычислимых (с полиномиальной сложностью) функций для этих моделей совпадают. Мерами сложности задач для таких компьютеров наряду со сложностью алгоритма могут быть и физические параметры: энергия, необходимая для решения задачи, физический объем компьютера и др.
Несколько лет назад были предложены качественно новые вычислительные модели — молекулярный компьютер и квантовый компьютер, которые могут изменить представление о вычислимых функциях и для которых ограничения по рассеиваемой энергии не столь значительны. Конечно в современном мире такие вычислительные мощности не востребованы и для обычного офиса с лихвой хватает компьютеров Preon на базе Intel® Core™ i7.
Молекулярный компьютер
Молекулярный компьютер основан на использовании химических свойств молекул ДНК. Каждая молекула ДНК представляет собой двойную спираль, состоящую из комплементарных половин. Информация в ДНК представлена в алфавите из четырех букв А, С, Т, G. В двойной спирали блок А спирали соединяется с блоком Т комплементарной спирали, блок С соединяется с блоком G. Цепочке ATTGTC спирали соответствует цепочка TAACAG комплементарной спирали. При нагревании двойные спирали ДНК распадаются на одиночные и при наличии соответствующих комплементарных фрагментов могут быть достроены до двойных.
В молекулярном компьютере информация представляется строками. Каждая строка состоит из цепочки неперекрывающихся попарно различных фрагментов, представленных символами в алфавите {А, Т, С, G} молекул ДНК (одиночная спираль) с возможно присоединенными комплементарными спиралями— стикерами (от англ. sticker— наклейка) для некоторых фрагментов. В соответствии с законом комплементарности, код стакера однозначно определяется кодом фрагмента.
Для каждого фрагмента цепочки соответствующий стикер, как комплементарная спираль ДНК может быть присоединен или удален.
Каждый фрагмент цепочки представляет собой один двоичный разряд строки, который может быть взаимно однозначно сопоставлен булевой переменной или промежуточной булевой функции. Если фрагмент цепочки снабжен стакером, то значение соответствующего разряда строки равно 1, если не снабжен, то 0.
Молекулярный компьютер может выполнять следующие базовые операции:
1) объединение двух множеств строк в одно множество;
2) разделение множества строк на два таких подмножества, что в одно подмножество попадают те строки, в которых значение бита на данной позиции равно 0, а в другое подмножество — строки, в которых значение бита на этой же позиции равно 1;
3) установка данного двоичного разряда строки в состояние 1;
4) установка данного двоичного разряда строки в состояние 0.
Эти операции, а также считывание результата выполняются с использованием физических и химических механизмов. Например, объединение двух множеств строк реализуется выливанием их содержимого, переведенного в состояние раствора, в общий сосуд. Разделение множества строк можно выполнять с помощью нагрева или электрофореза (пропускания постоянного тока через раствор). Установка бита на данной позиции строки в состояние 1 выполняется добавлением в раствор соответствующих стакеров. Лишние стакеры удаляются фильтрацией. Длительность вычислений на молекулярном компьютере оценивается в сотни часов.
На сегодняшний день задача вскрытия ключа шифра на молекулярном компьютере решается перебором. Основное преимущество молекулярного компьютера— высокая параллельность и малая энергоемкость вычислений — реализуется одновременным проведением вычислений с большим множеством строк.
Сложность задачи по отношению к молекулярному компьютеру оценивается требуемым объемом раствора (один литр раствора содержит примерно 1030 молекул ДНК).
Например, для вскрытия ключа длиной 256 бит требуется порядка 1040 литров раствора.
Квантовый компьютер
Другой «экзотический» вычислитель — гипотетический квантовый компьютер, позволяющий с полиномиальной сложностью решать задачи разложения составного числа и логарифмирования в произвольных группах вычислимого порядка. Например, задача разложения на множители числа длины L бит может быть решена со сложностью 0(L2). Однако несмотря на то, что алгоритмы для квантового компьютера существуют, проблема создания его работающей модели далека от решения. Квантовый компьютер, как и молекулярный, удобен для решения лишь немногих задач.
Информация в квантовом компьютере представлена квантовыми битами— кубитами (от англ. qubit = quantum bit). Бит информации представлен квантовой частицей, которая может находиться в двух состояниях. Состояние частицы может характеризоваться ее спином («спин вверх» или «спин вниз»), поляризацией (для квантов света— горизонтальная или вертикальная) и т. п.
Квантовая частица, находящаяся в двух возможных ортогональных состояниях 0 или 1, характеризуется вектором этих состояний (волновой функцией), где а, Р— комплексные амплитуды. Нормализацией амплитуд можно получить равенство |а|2 + |Р|2 = 1. Тогда значения |а|2 и |Р|2 можно интерпретировать как вероятность нахождения частицы в состоянии 0 или 1.
В отличие от обычного бита, представляющего 0 или 1, кубит может находиться в суперпозиции этих состояний. Однако при измерении кубита его состояние фиксируется.
Одним из фундаментальных ограничений на традиционные компьютеры является энергетическая необратимость переключения логического элемента из одного состояния в другое: при переключении энергия необратимо рассеивается. Поэтому для создания мощного компьютера требуется мощный источник питания, а также вентилятор для охлаждения.
Квантовый компьютер позволяет реализовать переключение из одного состояния в другое без рассеивания энергии. Для этого необходимо, чтобы реализуемые отображения для всевозможных состояний квантовой системы, состоящей из кубитов, задавали биекцию на множестве из 2й элементов (состояний системы). Это условие является необходимым для реализации такого отображения на квантовом компьютере.
Если квантовый компьютер дает решение задачи, то оно должно быть наблюдаемым. Это значит, что при измерении состояния квантового регистра результат измерения с большой вероятностью должен соответствовать решению задачи.
Автор: kozanostra777