Дискретное логарифмирование
Даны числа $a$, $b$ и $m$. Необходимо найти такой $x$, что $a^x = b \mod m$. При этом $gcd(a, m) = 1$, но $m$ не обязано быть простым.
Ответ есть не всегда, к примеру, при $a = 1$ и $b \neq 1$.
Сделаем корневую декомпозицию. Известно, что $x \in [0, m - 1]$. Пусть $k = \left\lfloor \sqrt{m} \right\rfloor$. Посчитаем числа вида $a^{k n}$ для $0 \le n \le \left\lceil \sqrt{m} \right\rceil $ и положим их в unordered_map. Пусть ответ — это $x$. $x = ki - j$, где $0 \le j < k$.
Тогда равенство можно записать как $a^{ki} = b \cdot a^j \mod p$. Числа слева у нас сохранены. Осталось последовательно домножать $b$ на $a$, пока такое число не попадется среди сохраненных.
Получается асимптотика $O(\sqrt{m})$.
Это хорошо, но на выполнение $n$ запросов уйдет $O(n \sqrt{m})$ времени.
Давайте делать лучше. Пусть $m$ — это $2$, $4$, $p^k$ или $2 \cdot p^k$. Найдем заранее $g$ — первообразный корень по модулю $m$ (он как раз существует ровно для таких $m$) и число $\varphi(m)$. Это можно сделать за $\sqrt{m}$. Затем вместо нахождения логарифма $b$ с основанием $a$, мы будем искать логарифмы обоих чисел по основанию $g$, а потом их надо будет просто поделить друг на друга по модулю $\varphi(m)$.
Заметим, что если мы всегда логарифмируем с фиксированным основанием, то первый шаг, на котором мы насчитываем все числа вида $g^{kn}$ можно не выполнять каждый раз, а только один раз в самом начале. Тогда можно взять $k \neq \sqrt{m}$.
Первая фаза работает за $m / k$ и выполняется один раз. Тогда фаза подсчета работает за $O(k)$. Асимптотика — $O(m/k + nk)$. Возьмем $m/k = nk$ для оптимальной асимптотики. $k = \sqrt{m/n}$. Время работы $O(\sqrt{mn} + n \log m)$.