Метод "шаг младенца, шаг гиганта" (baby-step giant-step) - это алгоритм для решения уравнений в целочисленных модулярных группах. Он используется для нахождения дискретного логарифма и основан на идее представления множества возможных значений целочисленного логарифма в виде двух подмножеств, одно из которых маленькое, а другое - большое. Для решения уравнения 2x mod 29 = 21 методом "шаг младенца, шаг гиганта" нужно выполнить следующие шаги: 1. Находим размер маленького и большого подмножеств. Обычно маленькое подмножество выбирается таким образом, чтобы его размер был примерно квадратным корнем из порядка группы, то есть в данном случае примерно 5 (количество элементов в группе Z29*). За размер маленького подмножества возьмем 5. 2. Составляем все возможные комбинации чисел из маленького подмножества. Рассчитываем значение 2^i mod 29 для каждого числа i из маленького подмножества. Эти значения сохраняем в таблице. 3. Вычисляем величину h = 2^5 mod 29 и ищем все значения 21*h^j mod 29 для j из интервала [0,4]. Эти значения также сохраняем в таблице. 4. Ищем одинаковые значения из таблицы, т.е. такие числа x и j, что 2^x mod 29 = 21*h^j mod 29. Это и есть решение уравнения. Рассчитаем значения из таблицы: Маленькое подмножество: i | 2^i mod 29 --|----------- 1 | 2 2 | 4 3 | 8 4 | 16 5 | 3 Большое подмножество: j | 21*h^j mod 29 --|--------------- 0 | 1 1 | 21 2 | 23 3 | 16 4 | 7 Вычисляем все возможные пары значений x и j из таблиц, чтобы найти одинаковые i | 2^i mod 29 | 21*h^j mod 29 | x+j*5 --|-----------|---------------|------ 1 | 2 | 1 | 6 2 | 4 | 21 | 11 3 | 8 | 23 | 13 4 | 16 | 16 | 24 5 | 3 | 7 | 8 Таким образом, решение уравнения 2x mod 29 = 21 равно 24 (модуль группы Z29*). Действительно, 2^24 mod 29 = 21. Проверим: 2*24 mod 29 = 19 2*19 mod 29 = 9 2*9 mod 29 = 18 2*18 mod 29 = 7 2*7 mod 29 = 14 2*14 mod 29 = 28 2*28 mod 29 = 27 2*27 mod 29 = 25 2*25 mod 29 = 21 Таким образом, мы действительно получили правильный ответ. Метод "шаг младенца, шаг гиганта" позволяет решить дискретные логарифмы достаточно эффективно, в O(√n) времени и O(√n) памяти, где n - порядок группы. Он широко применяется в криптографии для шифрования и создания цифровых подписей.