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

Задача поиска дискретного логарифма в Z *, где p – простое число, а также в группе точек эллиптической кривой над конечным полем считается неразрешимой для рандомизированных классических компьютеров. Дело в том, что любому (возможно, рандомизированному) алгоритму для решения этой задачи на классическом компьютере потребуется время, суперполиномиальное относительно количества бит, необходимых для описания входных значений. Лучшим классическим алгоритмом для нахождения дискретных логарифмов в Z*, где p – простое число, является адаптация Гордоном [ ] метода решета числового поля, которая выполняется за время exp(O((logp)1/3(loglogp)2/3)).

В ходе своих революционных исследований Шор [ ] предложил эффективный квантовый алгоритм для поиска дискретного логарифма в любой группе G; его алгоритм работает за время, полиномиальное относительно размера входных данных в битах.

Результат 1 [9]. Существует квантовый алгоритм, решающий задачу дискретного логарифмирования в любой группе G на n-битных входных данных за время O(n3) с вероятностью не менее 3/4.

Алгоритм Шора [ ] для решения задачи дискретного логарифмирования использует эффективную квантовую процедуру для реализации унитарного преобразования, известного как квантовое преобразование Фурье. Его исходный алгоритм давал эффективную процедуру выполнения квантового преобразования Фурье только над группами вида Zr, где r – «гладкое» целое число; тем не менее, он показал, что этого достаточно для решения задачи дискретного логарифмирования в общем случае. В данной статье приводится более современное описание алгоритма Шора. В частности, используется результат Хейлз и Холлгрена [ ], который показывает, что квантовое преобразование Фурье над любой конечной циклической группой Zr может быть эффективно аппроксимировано с обратно-экспоненциальной точностью.

Предполагаемая неразрешимость задачи дискретного логарифмирования лежит в основе нескольких криптографических алгоритмов и протоколов. Первый пример криптографии с открытым ключом, а именно обмен ключами с помощью протокола Диффи-Хеллмана [2], использует дискретные логарифмы, обычно в группе Z* для простого числа p. Безопасность алгоритма цифровой подписи, являющегося национальным стандартом США (подробности и ссылки см. в [ ]), зависит от предполагаемой неразрешимости задачи дискретного логарифмирования в Z*, где p – простое число. Криптосистема с открытым ключом ElGamal [3] и ее производные используют дискретные логарифмы в соответствующим образом выбранных подгруппах Z*, где p – простое число. Более поздние варианты применения включают криптографию на эллиптических кривых [6], где группа состоит из группы точек эллиптической кривой над конечным полем.