Квантовый криптоанализ



Квантовый криптоанализ - часть 2


Квантовая факторизация

Похоже, что разложение больших чисел лежит за пределами способностей любого реального компьютера и до тех пор, пока математики или компьютерные учёные не найдут эффективного алгоритма разложения, криптосистемы с открытым ключом останутся безопасными. Или нет? Как оказывается, нет; классическая, чисто математическая, теория вычислений является неполной просто потому, что она не описывает все физически возможные вычисления. В частности, она не описывает вычисления, которые могут быть произведены квантовыми устройствами. В самом деле, недавняя работа в области квантовых вычислений показывает, что квантовые компьютеры способны разложить число гораздо быстрей любого классического компьютера.

Квантовые компьютеры могут вычислять быстрей, потому что они принимают в качестве ввода не одно число, а когерентную суперпозицию множества различных чисел, после чего могут производить вычисления (последовательность единичных операций) на всех этих числах одновременно. Это можно представить как массивное параллельное вычисление, но вместо множества процессоров, работающих параллельно, мы имеем только один квантовый процессор, осуществляющий вычисление, которое воздействует на все числа в векторе. Для того, чтобы увидеть, как это работает, позвольте описать разложение Шора, использующее квантовый компьютер, составленных из двух квантовых регистров.

Математика разложения

Квантовое разложение целого числа N основано на вычислении периодичности функции FN(x) = a^x mod N. Математическая спецификация этой функции означает: выберите произвольное число а между 0 и N, затем возведите его в степени x, разделите на N и запомните остаток от деления, который будет являться значением функции. Выясняется, что с увеличением степени числа a, остатки от деления формируют повторяющуюся последовательность с периодом, который мы обозначим r. Как только r найден, множители числа N могут быть получены вычислением наименьшего общего частного числа N и чисел a^(r/2) +/- 1. К счастью, простой и очень эффективный алгоритм для вычисления наименьшего общего частного был найден ещё в 300 году нашей эры. Алгоритм, описанный в *Элементах* Эвклида - наистарейшем греческом научном труде по математике - достиг нас в своём первоначальном состоянии (просмотрите ваши школьные учебники в качестве пособия).

Допустим, мы хотим разложить число 15, используя этот метод. Пусть а=11. Для увеличивающегося x функция 11^x mod 15 формирует повторяющуюся последовательность 1, 11, 1, 11, 1, 11, ... Период r=2. Вычисляем промежуточные коэффициенты a^(r/2)+1=12, a^(r/2)-1=10. Теперь мы берём наименьшее общее частное чисел 10 и 15, и 12 и 15, что даёт нам соответственно 5 и 3 - два множителя числа 15. Классически, подсчёт r является таким же трудным, как и попытка разложить N, используя технику последовательного перебора делителей, то есть время выполнения вычислений возрастает экспоненциально при увеличении цифр в N. Квантовые компьютеры могут найти r в течении времени, которое растёт только как квадратичная функция от количества цифр в N.

<


Содержание  Назад  Вперед