Математика / Арифметика и теория чисел
Алгоритм baby-step giant-step для дискретного логарифма
Алгоритм baby-step giant-step находит x из a^x ≡ b (mod p), если a имеет подходящий конечный порядок. Он разбивает показатель на блоки размера m≈√n, сохраняет малые шаги и сопоставляет их с крупными шагами обратной степени.
Формула
Малые степени образуют таблицу, а правая часть движется обратными блоками до совпадения.
Обозначения
- $a$
- основание дискретного логарифма, элемент группы
- $b$
- Правая часть уравнения; проверяется принадлежность подгруппе, элемент группы
- $x$
- искомый показатель, класс modulo n
- $n$
- порядок подгруппы, порождённой a, элементы
- $m$
- размер блока шагов, элементы
- $i,j$
- индексы крупного и малого шага, целые
- $p$
- Простой модуль, —
Условия применения
Модуль p прост, 1 ≤ a,b < p, точный порядок основания a равен n. Требуется показатель x modulo n. Сначала можно проверить b^n ≡ 1 (mod p); в циклической группе ненулевых вычетов это проверяет принадлежность подгруппе порядка n. Для m = ceil(√n) сравнивают a^j и b·a^(−im) при 0 ≤ i,j < m.
Ограничения
Таблица требует O(√n) памяти и времени, поэтому метод не ломает корректно выбранные криптографические группы. Если порядок a неизвестен или b вне подгруппы, найденное совпадение нельзя интерпретировать как логарифм в заявленном диапазоне. При составном модуле нужны условия обратимости и аккуратная работа с порядком; при нескольких решениях указывают класс по модулю порядка.
Подробное объяснение
Идея алгоритма — заменить один перебор n показателей двумя переборами примерно по √n. Разложим x=im+j, где 0≤j<m. Тогда a^x=a^(im+j)=a^(im)a^j=b, поэтому a^j=b·a^(−im). Левая часть заранее заносится в таблицу малых шагов, а правая вычисляется последовательным умножением на a^(−m).
Для каждого i ищут совпадение между baby[j]=a^j и giant[i]=b·(a^(−m))^i. Если giant[i]=baby[j], то a^j=b·a^(−im), откуда a^(im+j)=b и x=im+j. Проверка подстановкой обязательна: хеш-таблица может хранить только первый индекс, а ошибки в порядке или обратном элементе меняют результат.
Размер m выбирают из порядка n, а не из самого простого модуля p. Если порядок основания меньше p−1, решения повторяются по этому порядку; найденный показатель приводят к диапазону. В мультипликативной группе modulo простого p обратный элемент существует для каждого ненулевого остатка, но принадлежность b подгруппе всё равно проверяют возведением в степень n.
Метод демонстрирует классический компромисс время–память: полный перебор использует O(1) памяти и O(n) шагов, BSGS — O(√n) времени и O(√n) памяти. Для больших криптографических групп это уже огромная таблица, поэтому применяют Pollard lambda/rho для логарифмов или параметры, рассчитанные на заданную стойкость.
Baby-step giant-step решает задачу конечной группы, а не вычисление вещественного логарифма и не использует ln. Все операции происходят в конечной группе, а знак минус в a^(−im) означает умножение на обратный элемент, а не отрицание остатка.
Как пользоваться формулой
- Определите порядок n основания a и убедитесь, что b находится в подгруппе; задайте m=ceil(sqrt(n)).
- Постройте таблицу a^j mod p для j от 0 до m−1 и сохраните для каждого остатка соответствующий индекс j.
- Найдите обратный элемент a^m modulo p и положите giant=b; это значение соответствует крупному индексу i=0.
- Для каждого i проверяйте giant в таблице; после проверки заменяйте giant на giant·a^(−m) modulo p.
- При совпадении с baby[j] вычислите x=im+j, приведите его modulo n и проверьте a^x≡b.
- Если все m крупных шагов завершены без совпадения, решения в выбранной подгруппе нет либо неверно задан её порядок.
- При повторяющихся остатках храните подходящие индексы или сообщите все решения, отличающиеся на порядок n.
Историческая справка
Baby-step giant-step обычно связывают с Дэниелом Шэнксом и вычислительной теорией чисел XX века. Метод разбивает показатель на короткую часть и номер блока, заменяя линейный перебор встречей двух списков. Современные курсы криптографии рассматривают его как базовый пример компромисса времени и памяти.
В университетских лекциях Стэнфорда и Висконсина алгоритм сопоставляют с другими методами дискретного логарифмирования. Он требует таблицу примерно квадратного корня из порядка основания и имеет детерминированную проверку найденного показателя. Методы Полларда для логарифмов позволяют экономить память при иной организации поиска.
Важно различать rho-факторизацию и rho-дискретный логарифм: одинаковая идея столкновений используется для разных задач. Baby-step giant-step здесь работает с показателями в подгруппе, а не извлекает делитель модуля. Его учебное значение — точное объяснение того, почему встреча a^j и b·a^(−im) восстанавливает показатель im+j.
Историческая линия формулы
Алгоритм обычно называют baby-step giant-step Шэнкса по работам Дэниела Шэнкса о дискретных логарифмах. Это meet-in-the-middle метод: авторство относится к конкретному разбиению показателя и таблице, а не к отдельной операции возведения в степень.
Пример
Решим 2^x ≡ 13 (mod 23). Основание 2 имеет порядок 11: 2¹¹ ≡ 1, а 2 ≠ 1 и 11 простое. Берём m = ceil(√11) = 4. Таблица малых шагов для j = 0,1,2,3 содержит соответственно 1, 2, 4, 8. Крупный шаг умножает на обратный к 2⁴ = 16 остаток. Он равен 13, поскольку 16·13 = 208 = 9·23 + 1. При i = 0 значение равно 13 и в таблице отсутствует. При i = 1 получаем 13·13 = 169 ≡ 8, что совпадает с j = 3. Значит, x = 1·4 + 3 = 7 modulo 11. Независимая проверка: 2⁷ = 128 = 5·23 + 13. Все числа безразмерны. Для другого значения b = 5 предварительная проверка даёт 5¹¹ ≡ 22, поэтому решения в подгруппе основания 2 нет; перебирать таблицу в таком случае необязательно.
Частая ошибка
Нельзя брать m из p вместо порядка основания: таблица и число крупных шагов должны покрывать показатель modulo n. Частая ошибка — использовать a^m вместо обратного элемента; giant-шаг должен умножать на a^(−m). Нельзя объявлять отсутствие решения только по плохому порядку: сначала проверяют b^n≡1. Индекс x=im+j может выйти за диапазон и должен быть приведён modulo n. Наконец, проверка a^x mod p обязательна, особенно если таблица содержит повторяющиеся остатки.
Практика
Задачи с решением
Другой показатель
Условие. Решите 2^x ≡ 4 (mod 23) при порядке основания 11 и m = 4.
Решение. Уже при i = 0 значение giant = 4 есть в таблице как j = 2. Поэтому x = 0·4 + 2 = 2 modulo 11. Проверка: 2² = 4.
Ответ. x ≡ 2 (mod 11).
Нет решения в подгруппе
Условие. Объясните, почему для 2^x≡5 (mod 23) BSGS не обязан выдавать показатель.
Решение. Подгруппа основания 2 имеет порядок 11. Вычисление 5¹¹ mod 23 даёт 22, а не 1, поэтому 5 не принадлежит этой подгруппе. Решения нет.
Ответ. Решения нет в подгруппе <2>.
Дополнительные источники
- https://crypto.stanford.edu/cs355/19sp/lec11.pdf
- https://pages.cs.wisc.edu/~cs812-1/lec25.pdf
- https://cacr.uwaterloo.ca/hac/about/chap3.pdf
Связанные формулы
Математика
Мультипликативный порядок: минимальный период степеней
Мультипликативный порядок обратимого остатка — наименьшая положительная степень, в которой он возвращается к единице. Этот период делит φ(m) и позволяет сокращать показатели точнее, чем одна теорема Эйлера.
Математика
Быстрое возведение в степень по модулю двоичным методом
Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ.
Математика
Обратный элемент по модулю через расширенный алгоритм Евклида
Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.
Математика
Малая теорема Ферма: степени по простому модулю
Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.