11.2 Постановка задачи

Пусть  -- некоторая мультипликативно записываемая группа, а и  -- некоторые элементы группы , связанные равенством при некотором целом . Любое целое , удовлетворяющее уравнению , называется дискретным логарифмом элемента по основанию . Задача дискретного логарифмирования в группе состоит в отыскании по данным и вышеуказанного вида (при этом может быть или не быть фиксированным) некоторого дискретного логарифма по основанию . Если имеет бесконечный порядок, то дискретный логарифм любого элемента по основанию определен однозначно. В противном случае все дискретные логарифмы по основанию можно получить из некоторого такого дискретного логарифма по формуле , где  -- порядок элемента , а параметр пробегает .

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