Математика / Арифметика и теория чисел

Алгоритм baby-step giant-step для дискретного логарифма

Алгоритм baby-step giant-step находит x из a^x ≡ b (mod p), если a имеет подходящий конечный порядок. Он разбивает показатель на блоки размера m≈√n, сохраняет малые шаги и сопоставляет их с крупными шагами обратной степени.

Опубликовано: Обновлено:

Формула

$$x=im+j,\quad a^j=b\,a^{-im}\pmod p,\quad m=\lceil\sqrt n\rceil$$
Схема Два направления BSGS
x=im+jbaby: a^jgiant: b·a^−imсовпадениеx=im+j, проверка a^x≡b

Малые степени образуют таблицу, а правая часть движется обратными блоками до совпадения.

Обозначения

$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) означает умножение на обратный элемент, а не отрицание остатка.

Как пользоваться формулой

  1. Определите порядок n основания a и убедитесь, что b находится в подгруппе; задайте m=ceil(sqrt(n)).
  2. Постройте таблицу a^j mod p для j от 0 до m−1 и сохраните для каждого остатка соответствующий индекс j.
  3. Найдите обратный элемент a^m modulo p и положите giant=b; это значение соответствует крупному индексу i=0.
  4. Для каждого i проверяйте giant в таблице; после проверки заменяйте giant на giant·a^(−m) modulo p.
  5. При совпадении с baby[j] вычислите x=im+j, приведите его modulo n и проверьте a^x≡b.
  6. Если все m крупных шагов завершены без совпадения, решения в выбранной подгруппе нет либо неверно задан её порядок.
  7. При повторяющихся остатках храните подходящие индексы или сообщите все решения, отличающиеся на порядок 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

Связанные формулы

Математика

Мультипликативный порядок: минимальный период степеней

$\operatorname{ord}_m(a)=\min\{k\ge1:a^k\equiv1\pmod m\},\qquad\operatorname{ord}_m(a)\mid\varphi(m)$

Мультипликативный порядок обратимого остатка — наименьшая положительная степень, в которой он возвращается к единице. Этот период делит φ(m) и позволяет сокращать показатели точнее, чем одна теорема Эйлера.

Математика

Быстрое возведение в степень по модулю двоичным методом

$a^n\bmod m,\qquad a^{2q}=(a^q)^2,\quad a^{2q+1}=a(a^q)^2$

Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ.

Математика

Обратный элемент по модулю через расширенный алгоритм Евклида

$au+mv=1\quad\Longrightarrow\quad a^{-1}\equiv u\pmod m$

Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.

Математика

Малая теорема Ферма: степени по простому модулю

$a^{p-1}\equiv1\pmod p,\quad p\text{ простое},\quad p\nmid a$

Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.