Выводы
•Квантовый компьютер сможет найти запись в случайной базе данных гораздо быстрее чем классический компьютер.
•В случайной(неотсортированной) базе данных с N записями обычный компьютер будет в среднем делать N / 2 поисковых попыток прежде чем он обнаружит искомую запись.
•Для поиска на квантовом компьютере в той же
базе данных размера N потребуется всего 
N попыток (алгоритм Гровера)
25
Криптосистема РША
Рис. 1. Схематическое описание криптосистемы РША
26
Квантовый компьютер и криптосистема РША
•В ранних криптостойких системах использовались целые числа с 400 болеедвоичными числами. (1994г.)
•На компьютере 1994г. потребуется~109 лет для разложения такого числа на множители.
•Квантовый компьютер, равный по скорости счета такомукомпьютеру, справится с этой задачей за секунды (алгоритм Шора)
27
Пример длинного числа
p |
q |
n |
Стойкость алгоритма РША основывается на вычислительной сложности решения задачи факторизации модуля n=nq
28
Сравнение классическогои квантового компьютера для RSA
Количество
Операции
факторизации
Современные
требования
Кол-во бит Модуля
29
Алгоритм факторизациичисла на квантовом компьютере Питера Шора, 1994г.
30