-
Математика
-
Теория чисел
-
Алгоритм Шенкса
Дискретное логарифмирование — задача обращения функции \( g^x \) в некоторой конечной мультипликативной группе \( G \). Наиболее часто задачу дискретного логарифмирования рассматривают в мультипликативной группе кольца вычетов или конечного поля, а также в группе точек эллиптической кривой над конечным полем. Для заданных \( g \) и \( a \) решение \( x \) уравнения \( g^x = a \) называется дискретным логарифмом элемента \( a \) по основанию \( g \). В случае, когда \( G \) является мультипликативной группой кольца вычетов по модулю \( p \), решение называют также индексом числа \( a \) по основанию \( g \). Индекс числа \( a \) по основанию \( g \) гарантированно существует, если \( g \) является первообразным корнем по модулю \( p \).
Задача сводится к нахождению целого числа \( x \), для которого выполняется:
\[ g^x = a \bmod p \]
Алгоритм Шенкса основан на переборе \( x \), таких, что \( x = im - j \), где \( m = \left \lfloor \sqrt{p} \right \rfloor + 1 \) и \( 0 \leq i \leq m \) и \( 0 \leq j < m \). Ограничение на \( i \) и \( j \) следует из того, что порядок группы не превосходит \( m \), а значит достаточно перебрать все \( x \) в диапазоне \( \left[0; m\right) \). Отсюда следует, что
\[ \alpha^{im} = \beta \alpha^j \]
Алгоритм предварительно вычисляет \( \alpha^{im} \) для некоторых значений \( i \) при фиксированном \( m \). Затем следует перебрать всевозможные значения \( j \) в правой части равенства для того, чтобы равенство выполнялось. Таким образом проводятся испытания на выполнение равенства для каких-либо значений \( j \), предварительно вычислив \( \alpha^{im} \).