Алгоритм Гельфонда - Шенкса
$$a^{x} = b\ mod\ p$$, найти $$x$$ при известных $$a,\ b\ и\ p$$
подробнее
Онлайн калькулятор для решения задачи дискретного логарифмирования. То есть, для сравнения $$a^{x}\ =\ b\ mod\ p$$ калькулятор найдет значения показателя степени — x методом «Шаг младенца — шаг великана».
Как пользоваться:
В соответствующие поля заносятся известные значения из уравнения. После нажатия кнопки «Вычислить» калькулятор выдаст неизвестное значение показателя степени, если для указанных данных существует решение. Если выставлена галочка «подробнее» калькулятор выдаст этапы решения.
Ограничения:
Все 3 числа должны быть натуральными (1, 2, …) Числа a и b должны быть меньше чем модуль p. Модуль p должен быть простым. Максимальное введенное число должно быть менее 1 000 000.
В открытой литературе этот метод «Шаг младенца — шаг великана» был впервые описан Шенксом (Daniel Shanks). Это был один из первых методов, который показал, что задача вычисления дискретного логарифма может быть решена значительно быстрее, чем методом перебора.
Алгоритм:
Шаг 1. Сначала берутся два целых числа m и k , такие, что
$$mk\ >\ p$$
Как правило $$m=k=[\sqrt[2]{p}] + 1$$.
Шаг 2. Вычисляются два ряда чисел:
$$a^{m},\ a^{2m},\ …\ ,\ a^{km}\ mod\ p$$
$$b,\ ba,\ ba^{2},\ …\ ,\ ba^{m-1}\ mod\ p$$
(все вычисления проводятся по модулю p).
Шаг 3. Найдем такие $$i$$ и $$j$$ , для которых выполняется равенство
$$a^{im} = ba^{j}$$
Иными словами, найдем во втором ряду такое число, которое присутствует и в первом ряду. Запомним показатели степени $$im$$ и $$j$$, при которых данные числа получились.
Неизвестная степень $$x = im − j$$.
В разделе примеры ниже можно разобрать алгоритм на конкретном примере.
Найдем решение уравнения $$3^{x} = 5\ mod\ 11$$, используя метод «шаг младенца, шаг великана»
-
- Возьмем $$m=k=[\sqrt[2]{p}] + 1$$; $$m=k=[\sqrt[2]{11}] + 1$$ ; $$m=k=4$$
- Вычислим 2 ряда чисел:
Все вычисления по модулю $$ p = 11$$
| $$i$$ | 1 | 2 | 3 | 4 |
| $$a^{im}\ mod(p)$$ | $$3^{1 * 4} = 3^4 = 4$$ | $$3^{2 * 4} = 3^8 = 5$$ | $$3^{3 * 4} = 3^{12} = 9$$ | $$3^{4 * 4} = 3^{16} = 3$$ |
| $$j$$ | 1 |
| $$ba^{j}\ mod(p)$$ | $$5 * 3^1 = 15 = 4$$ |
Видим, что сразу же при $$j = 1$$ мы получили число $$4$$, которое есть и в первой таблице при $$i = 1$$. Значит дальше считать не будем. Выписываем $$i = 1, j = 1, m = 4$$
Следовательно, $$x = im − j = 1 * 4 − 1 = 3$$.
Проверка:
$$3^3 = 5\ mod\ 11$$
$$27 = 5\ mod\ 11$$
$$5 = 5\ mod\ 11$$