Метод "шаг младенца, шаг гиганта" (Baby-Step Giant-Step) является алгоритмом решения уравнения вида a^x mod m = b, где a, x и m - заданные числа, b - результат возведения числа a в степень x по модулю m.
Для начала определим максимальное значение k - это целое число, ближайшее к √m, которое делится нацело.
k = floor(√m) + 1
Затем составляем два списка: список младенцев и список гигантов.
Список младенцев составляется путем вычисления a^j mod m для всех j в диапазоне [0, k). Т. е., если k = 5 и a = 3, то список младенцев будет выглядеть как {1, 3, 9, 27, 81}.
Список гигантов составляется путем вычисления b * a^-mk mod m для всех k в диапазоне [0, k). Т. е., если k = 5, a = 3 и b = 11, то список гигантов будет выглядеть как {11, 19, 36, 37, 9}.
Затем находим все совпадения между двумя списками, т. е. значения, которые присутствуют в обоих списках, и выбираем минимальное из них. Если совпадения нет, то решения уравнения не существует.
В нашем примере a = 3, m = 43 и b = 11. Находим k:
k = floor(√43) + 1 = 7
Составляем список младенцев для a = 3:
{1, 3, 9, 27, 81, 13, 39}
Затем составляем список гигантов для b = 11 и a = 3:
{11, 33, 22, 23, 39, 12, 1}
Обнаруживаем совпадение в 6-м элементе обоих списков (39), что означает, что:
3^6 mod 43 = 11 * 3^-42 mod 43
x = 6 - 42k, где k - любое целое число
x = 6 - 42 * 1 = -36 (mod 42)
x = 6 - 42 * 2 = -78 (mod 42)
x = 6 - 42 * 3 = -120 (mod 42)
... и т.д.
x = -36 (mod 42) = 6
Ответ: x = 6.
