Квантовый алгоритм для решения задачи дискретного логарифмирования: различия между версиями

Описание алгоритма приведено ниже. Предполагается знакомство с квантовой нотацией. Достаточное представление о квантовых вычислениях можно найти в книге Нильсена и Чуаня [8]. Пусть (G; a; b, f) – экземпляр задачи дискретного логарифмирования, где f – заданная верхняя граница на порядок a в G. То есть существует положительное целое число r < f, такое, что ar = 1. Используя эффективный квантовый алгоритм поиска порядка, также разработанный Шором [9], можно предположить, что порядок a в G известен и представляет собой наименьшее положительное целое число r, удовлетворяющее ar = 1. Время выполнения алгоритма Шора для поиска порядка составляет O((logf)3). Пусть e > 0. Алгоритм дискретного логарифмирования работает на трех регистрах, из которых первые два имеют длину по t кубитов, где t := O(log r + log(l/e)), а третий регистр достаточно велик, чтобы хранить элемент G. Пусть U обозначает унитарное преобразование, где ф обозначает побитовое исключающее ИЛИ. Если имеется доступ к обратимому оракулу для групповых операций в G, U может быть реализовано обратимо за время O(t3) путем многократного возведения в квадрат.