11.5 Рекомендуемая литература

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

Библиографию по алгоритмам дискретного логарифмирования до алгоритма Копперсмита включительно можно найти в книге Лидла и Нидеррайтера [ЛН, т. 1, стр. 227, т. 2, стр. 798-805]; библиографию таблиц, связанных с вычислениями в конечных полях, там же на стр. 670-672.

Всеобъемлющий обзор этой тематики до алгоритма Копперсмита включительно с полным списком литературы содержится в статье Одлыжко [Odl].

Введением в дискретное логарифмирование и его связь с криптографией может служить книга Коблица [Kob]).

В работе Баха [Ba] приведен обзор алгоритмов дискретного логарифмирования до алгоритма Копперсмита. В ней есть некоторые замечания об алгоритмах дискретного логарифмирования на эллиптических кривых (см. также [Kob]) и обзор вероятностных алгоритмов дискретного логарифмирования (см. также [Pom87]). Дан обзор работ, где исследуются случаи тех , для которых дискретное логарифмирование в проводится быстро.

Наилучшую оценку сложности из алгоритмов дискретного логарифмирования в произвольном группе вида , где  -- простое число, имеет алгоритм работы Гордона [Gord]. Для группы вида , где , -- простое число, наилучшую оценку сложности имеет недавно полученный алгоритм Адлемана и Де Марраиса [AM], делающий арифметических операций.

Подробный список литературы по дискретному логарифмированию за последние годы имеется в работе МакКарли [McC90]; в него включен также ряд зарубежных препринтов и технических сообщений.

Имеется также работа Эль Гамаля [ElG86] о дискретном логарифмировании в группе .

В работе Гольдрайха и Кушилевица [GK] рассматривается обобщение задачи дискретного логарифмирования для конечных абелевых групп и сложность некоторых связанных с дискретным логарифмированием задач.

Для задачи логарифмирования на эллиптической кривой в последнее время был получен ряд интересных результатов, показывающих, что в ряде случаев она может быть сведена к логарифмированию в конечных полях (см. [Сем], [MOV], [FR]).

С целью избежать опасности решения задачи дискретного логарифмирования на эллиптической кривой с помощью вложения в конечное поле, Бет и Шафер в работе [BSch] предложили примеры специальных эллиптических кривых, для которых такое вложение имеет достаточно высокую степень.

В 1991 г. Мурин в работе [Mor] предложил метод построения циклических эллиптических кривых большой простой мощности.

Можно также отметить работу Шизуйа [Shiz] о сложности дискретного логарифмирования на эллиптических кривых.