Криптографы интересуются дискретными логарифмами следующих трех групп:
— Мультипликативная группа полей простых чисел: G¥(p)
— Мультипликативная группа конечных полей степеней 2: GF(2")
— Группы эллиптической кривой над конечными полями F: EC(F)
Безопасность многих алгоритмов с открытыми ключами основана на задаче поиска дискретных логарифмов, поэтому эта задача была глубоко изучена. Хороший подробный обзор этой проблемы и ее наилучшие решения на соответствующий момент времени можно найти в [1189, 1039]. Лучшей современной статьей на эту тему является [934].
Если р является простым числом и используется в качестве модуля, то сложность поиска дискретных лог а-рифмов в GF(p) по существу соответствует разложению на множители числа п того же размера, где п - это произведение двух простых чисел приблизительно равной длины [1378,934]. То есть: