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

Предполагаемая неразрешимость задачи дискретного логарифмирования лежит в основе нескольких криптографических алгоритмов и протоколов. Первый пример криптографии с открытым ключом, а именно обмен ключами с помощью протокола Диффи-Хеллмана [2], использует дискретные логарифмы, обычно в группе <math>\mathbb{Z}^*_p</math> для простого числа p. Безопасность алгоритма цифровой подписи, являющегося национальным стандартом США (подробности и ссылки см. в [7]), зависит от предполагаемой неразрешимости задачи дискретного логарифмирования в <math>\mathbb{Z}^*_p</math>, где p – простое число. Криптосистема Эль-Гамаля с открытым ключом [3] и ее производные используют дискретные логарифмы в соответствующим образом выбранных подгруппах <math>\mathbb{Z}^*_p</math>, где p – простое число. Более поздние варианты применения включают криптографию на эллиптических кривых [ ], где группа состоит из группы точек эллиптической кривой над конечным полем.