Метод "шаг младенца, шаг гиганта" (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.