Задача дискретного логарифмирования на эллиптической кривой.

Задача дискретного логарифмирования (DLP – Discrete Logarithm Problem) – это задача поиска решения уравнения в кольце с простым .

Определение 4.Пусть – эллиптическая кривая над полем и пусть – точки на . Задача дискретного логарифмирования на эллиптической кривой (ECDLP – Elliptic Curve Discrete Logarithm Problem) – это задача поиска такого, что . Величину называют дискретным логарифмом по основанию и обозначают .

В настоящее время задача ECDLP считается трудноразрешимой (неразрешимой с вычислительной точки зрения), если порядок точки – большое простое число.

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