Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

IMPROVING THE PERFORMANCE OF P. SHOR’S FACTORING QUANTUM ALGORITHM BY IMPROVING ITS CLASSICAL PART

Razumov P.V. 1 Smirnov I.A. 1 Cherсkesova L.V. 1 Safaryan O.A. 1 Pilipenko I.A. 1
1 Don State Technical University
The proposed article compares the quantum factorization algorithm of Peter Shor and the factorization algorithm of the ?-John Pollard method. As is well known, the quantum algorithm for factoring Shor consists of classical and quantum parts. In the classical part, it is proposed to use the Euclidean algorithm to find the greatest common divisor of numbers (GCD). However, there are quite a number of algorithms for finding the greatest common divisor of numbers. The authors of this article reviewed the results of calculations of eight algorithms, among which the algorithm with the highest GOD search speed was found. This allows the quantum algorithm as a whole to work faster. In turn, this provides a great potential for the practical application of the quantum Shor algorithm. Thus, the authors modified the standard quantum algorithm of P. Shor by replacing the binary NOD search algorithm with an iterative shift algorithm, canceling the random number generation operation and using the additive chain algorithm for fast exponentiation. The obtained modified Shor’s algorithm is distinguished by higher performance and speed in the implementation of factorization. The effectiveness of this modified algorithm turned out to be, in general, higher than that of the standard Shor algorithm, due to the improvement of its classical part. As a result, the performance of the algorithm increased by 50?%.
quantum algorithm
factorization
the greatest common divisor
qubit
binary algorithm
recursive algorithm
iterative algorithm

На сегодняшний день область квантовых вычислений постепенно выходит на ведущие позиции в области информационных технологий и вычислительной техники. Все большее внимание ученых и научных исследователей уделяется суперсовременной вычислительной модели, основанной на понятии кубита – квантового бита, призванной вытеснить давно известную модель, нашедшую применение практически во всех средствах вычислительной техники и основанной на понятии бита, которая была разработана Аланом Тьюрингом и Джоном фон Нейманом [1, 2].

Квантовым битом является некая квантовая система, которая до измерения находится в произвольной линейной суперпозиции двух базисных квантовых состояний, а в результате измерения с некоторой вероятностью принимает одно из двух возможных значений. С одной стороны, этот элемент является тем же битом, потому что принимает два значения, а с другой стороны – является квантовым, так как эти два значения находятся в суперпозиции друг с другом [3].

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

Одним из ярких примеров таких задач является задача факторизации некоторого числа, решением которой является поиск делителей этого числа [4].

Цель исследования: доказать преимущество квантового алгоритма перед алгоритмами других вычислительных моделей. Как известно, алгоритм Шора имеет квантовую и классическую части, что позволяет увеличить скорость вычисления алгоритма в целом, максимально модернизировав и упростив классическую часть. Несмотря на достоинства квантового алгоритма, он имеет свои недостатки, так как имеет классическую часть, которая выполняется на обычных компьютерах. Именно классическая часть является слабым звеном в алгоритме Шора. И поэтому, модернизировав и максимально упростив её, есть возможность увеличить скорость вычислений квантового алгоритма Шора.

Предполагаемая большая вычислительная сложность задачи факторизации лежит в основе криптостойкости некоторых алгоритмов шифрования с открытым ключом, таких как RSA. Более того, система взламывается однозначно, если известен хотя бы один из параметров ключей алгоритма RSA.

ρ-метод факторизации Полларда. Рассмотрим следующий алгоритм:

1. Рассмотрим последовательность целых чисел xn, такую, где каждое следующее число raz03.wmf. В этой последовательности x0 – небольшое число.

2. На каждом шаге будем вычислять значение raz04.wmf где j < i.

3. Если d ≠ 1, то вычисления заканчиваются. Найденное число d является делителем числа n. Если n/d не является простым числом, то процедуру можно продолжить, взяв вместо n число n/d.

Главным недостатком данного метода является выделение дополнительной памяти для хранения предыдущих значений xj. Заметим, что если raz05.wmf, то raz06.wmf. Поэтому, если пара (xi, xj) дает нам решение, то решение даст любая пара raz07.wmf [5].

Программная реализация алгоритма ρ-метода факторизации Полларда

raz08.wmf

raz09.wmf

raz10.wmf

raz11.wmf

}

raz13.wmf

raz14.wmf

raz15.wmf

raz16.wmf

raz17.wmf

}

raz19.wmf

Квантовый алгоритм Шора

Суть данного метода заключается в том, что задача факторизации сводится к задаче поиска периода функции. Когда период функции известен, факторизация осуществляется на классическом компьютере за полиномиальное время при помощи алгоритма Евклида. Квантовой части алгоритма отведено выполнение поиска периода функции. А классическая часть алгоритма сначала специальным образом готовит оную функцию, а потом проверяет найденный квантовой частью период на достаточность для решения задачи. Если период найден правильно (алгоритм вероятностный, так что может найти не то, что хочется), то задача решена. Если же нет, то квантовая часть алгоритма выполняется ещё раз. А поскольку проверка правильности решения для задачи факторизации очень проста (умножили два числа да сравнили с третьим), то эту часть алгоритма вообще можно не принимать во внимание с точки зрения подсчёта сложности [6].

Алгоритм факторизации Шора

1. Выбрать случайное число a, меньшее raz20.wmf.

2. Вычислить НОД (a, M). Это может быть сделано при помощи алгоритма Евклида.

3. Если НОД (a, M) не равен 1, то существует нетривиальный делитель числа M, так что алгоритм завершается (вырожденный случай).

4. В противном случае необходимо использовать квантовую подпрограмму поиска периода функции raz21.wmf.

5. Если найденный период r является нечётным, то нужно вернуться на шаг 1 и выбрать другое число a.

6. Если raz22.wmf, то вернуться на шаг 1 и выбрать другое число a.

7. Наконец, определить два значения raz23.wmf, которые и являются нетривиальными делителями числа M.

Важным является выбор количества кубитов, которые будут использованы в квантовой схеме. Необходимо выбрать такое количество кубитов q, чтобы выполнялось неравенство raz24.wmf. При выполнении данного равенства обеспечивается, что данного количества кубитов достаточно, чтобы достаточное количество раз выполнить функцию, для которой ищется период, чтобы сработала конструктивная интерференция [7].

Реализация квантового алгоритма Шора

Перед реализацией необходимо определить некоторые вспомогательные функции и константы.

raz25.wmf

Константа numberToFactor задаёт число, которое необходимо разложить на простые множители. Константа simpleNumber представляет собой взаимно простое число с предыдущей константой. Далее константы nofAncillas, nofWorkingOubits и nofOubits представляют количество вспомогательных и рабочих кубитов, а также общее количество кубитов в квантовой схеме.

Функция periodicFunction являет собой как раз ту периодическую функцию, задачу поиска периода которой и выполняет квантовая подпрограмма алгоритма Шора.

Далее реализуем квантовую схему в виде функции.

raz26.wmf

Данное определение соответствует нижеприведенной диаграмме квантовой схемы.

razum1.tif

Рис. 1. Диаграмма квантовой схемы

Сравнительный анализ данных алгоритмов на практике

Квантовый алгоритм факторизации Шора, как упоминалось ранее, можно условно разделить на две части – классическую и квантовую. Рассмотрим наиболее слабое место данного алгоритма, а именно классическую часть, которую можно модифицировать и модернизировать.

Классическая часть

В классической части для нахождения НОД предлагается использовать алгоритм Евклида, но, более того, существует достаточно большое количество алгоритмов нахождения наибольшего общего делителя пары чисел. Ниже рассмотрены результаты вычислений каждого из этих алгоритмов, среди которых требуется идентифицировать алгоритм с наименьшей скоростью выполнения поставленной задачи, что позволит квантовому алгоритму в целом работать несколько быстрее, что, в свою очередь, обеспечит больший потенциал для практического применения квантового алгоритма Шора.

В качестве исследуемых отобраны восемь наиболее распространенных алгоритмов нахождения НОД и произведена проверка их скорости вычисления на числах разной сложности. Номерам gcd 1 – gcd 8 соответствуют следующие названия:

1. Перебор от произвольного числа.

2. Перебор от минимального числа.

3. С разложением на делители.

4. Алгоритм Евклида рекурсивный.

5. Алгоритм Евклида итерационный.

6. Бинарный алгоритм рекурсивный.

7. Бинарный алгоритм итерационный.

8. Бинарный алгоритм итерационный со сдвигом.

Результаты вычислений представлены в табл. 1.

Таблица 1

Вычисления классических алгоритмов

 

10–100

100–1000

1000–10000

10000–100 000

100 000–1 000000

gcd 1

0,0040

0,0402

0,3531

1,7404

7,7908

gcd 2

0,0030

0,0305

0,2490

1,3123

7,4236

gcd 3

0,0028

0,0134

0,0436

0,1089

0,4675

gcd 4

0,0068

0,0150

0,0273

0,0277

0,0454

gcd 5

0,0010

0,0017

0,0025

0,0029

0,0036

gcd 6

0,0030

0,0064

0,0085

0,0099

0,0124

gcd 7

0,0012

0,0018

0,0020

0,0022

0,0026

gcd 8

0,0009

0,0014

0,0016

0,0018

0,0020

Самым эффективным алгоритмом является gcd8 (бинарный с итерационным сдвигом), а gcd 5 (алгоритм Евклида итерационный) является третьим по эффективности.

Наиболее рациональным является выбор алгоритма gcd 8 (бинарный алгоритм итерационный со сдвигом), причиной чему служит то, что он предназначен для решения весьма трудоёмких задач. В связи с этим данный алгоритм вряд ли будет применяться с практической точки зрения для чисел с малым диапазоном, меньших 1000. Рассчитывать среднюю эффективность алгоритма будем по следующей формуле:

raz27.wmf. (*)

Таким образом, использование данного алгоритма в среднем позволит вычислять нахождения НОД двух чисел на 29 % быстрее, чем при использовании стандартного алгоритма Евклида. В алгоритме, при формировании случайного числа а, используется операция генерации случайного числа, которая при вычислении не является достаточно быстрой и кибербезопасной. Поэтому было принято решение заменить эту операцию на n – M, где n < M. Рассчитанный результат средней эффективности алгоритма по формуле (*) составил 72 %. Результаты тестирования этих алгоритмов представлены в табл. 2.

Таблица 2

Вычисления преобразованного алгоритма

 

1–10

10–102

102–103

103–104

104–105

105–106

106–107

107–108

random

0,0019

0,0019

0,0021

0,0021

0,0021

0,0021

0,0021

0,0021

M-n

0,0005

0,0005

0,0006

0,0006

0,0006

0,0006

0,0006

0,0006

Стандартная операция возведения в степень также является недостаточно быстрой в данном алгоритме. Проанализировав все существующие алгоритмы, было принято решение использовать алгоритм аддитивных цепочек, средняя эффективность которого, согласно формуле (*), на 53 % выше по сравнению со стандартным алгоритмом. Результаты тестирования алгоритмов представлены в табл. 3.

Таблица 3

Вычисления алгоритма аддитивных цепочек

 

25

210

220

240

280

2160

2320

обычный

0,0008

0,0010

0,0014

0,0022

0,0039

0,0072

0,0139

Аддитивные цепочки

0,0008

0,0008

0,0009

0,0009

0,0009

0,0009

0,0009

Произведя модернизацию классической части алгоритма Шора, было произведено тестирование с целью вычисления секретной экспоненты d шифра RSA с ключом в 1024 бита. Результат вычислений с использованием алгоритмов ρ-метода Полларда, стандартного алгоритма Шора и предложенного авторами модифицированного алгоритма Шора представлен на рис. 2.

razum2.tif

Рис. 2. Сравнение алгоритмов

Исходя из результатов данного эксперимента, наблюдается преимущество предложенного авторами модифицированного квантового алгоритма Шора, модернизированного путем усовершенствования его классической части, которая работает на 50 % быстрее, чем в стандартном алгоритме П. Шора.

Таким образом, сравнивая стандартный и модифицированный авторами алгоритмы Шора и ρ-метод Полларда, можно отметить, что предложенный авторами алгоритм осуществляет процесс обработки данных существенно быстрее. Анализируя график, можно увидеть, что в зависимости от увеличения значения обрабатываемого числа, количество вычислений и затраченное на них время возрастает несущественно.

Заключение

Результаты исследования показывают преимущество квантовых алгоритмов вычислений перед традиционными не квантовыми алгоритмами, вычислительная мощность которых значительно меньше. Оба рассмотренных алгоритма (стандартный и модифицированный) отличаются своей высокой производительностью.

Из рис. 2 видно, что, в зависимости от увеличения значения обрабатываемого числа, количество вычислений и затраченное на них время возрастает несущественно.

Авторам удалось усовершенствовать квантовый алгоритм Шора так, что эффективность полученного алгоритма оказалась выше, чем у стандартного алгоритма, за счет усовершенствования классической части, которая работает на 50 % быстрее.