MAXimal

добавлено: 10 Jun 2008 18:08
редактировано: 23 Mar 2012 3:50

Дискретное логарифмирование

Задача дискретного логарифмирования заключается в том, чтобы по данным целым $a$ , $b$ , $m$ решить уравнение:

$a^x = b \pmod m,$

где $a$ и $m$ — взаимно просты (примечание: если они не взаимно просты, то описанный ниже алгоритм является некорректным; хотя, предположительно, его можно модифицировать, чтобы он по-прежнему работал).

Здесь описан алгоритм, известный как "baby-step-giant-step algorithm", предложенный Шэнксом (Shanks) в 1971 г., работающий за время за $O (\sqrt{m} \log m)$ . Часто этот алгоритм просто называют алгоритмом "meet-in-the-middle" (потому что это одно из классических применений техники "meet-in-the-middle": "разделение задачи пополам").

Алгоритм

Итак, мы имеем уравнение:

$a^x = b \pmod m,$

где $a$ и $m$ взаимно просты.

Преобразуем уравнение. Положим

$x = np - q,$

где $n$ — это заранее выбранная константа (как её выбирать в зависимости от $m$ , мы поймём чуть позже). Иногда $p$ называют "giant step" (поскольку увеличение его на единицу увеличивает $x$ сразу на $n$ ), а в противоположность ему $q$ — "baby step".

Очевидно, что любое $x$ (из промежутка $[0;m)$ — понятно, что такого диапазона значений будет достаточно) можно представить в такой форме, причём для этого будет достаточно значений:

$p \in \left[ 1; \left\lceil \frac{m}{n} \right\rc[...]$

Тогда уравнение принимает вид:

$a^{np-q} = b \pmod m,$

откуда, пользуясь тем, что $a$ и $m$ взаимно просты, получаем:

$a^{np} = b a^q \pmod m.$

Чтобы решить исходное уравнение, нужно найти соответствующие значения $p$ и $q$ , чтобы значения левой и правой частей совпали. Иначе говоря, надо решить уравнение:

$f_1(p) = f_2(q).$

Эта задача решается с помощью метода meet-in-the-middle следующим образом. Первая фаза алгоритма: посчитаем значения функции $f_1$ для всех значений аргумента $p$ , и отсортируем эти значения. Вторая фаза алгоритма: будем перебирать значение второй переменной $q$ , вычислять вторую функцию $f_2$ , и искать это значение среди предвычисленных значений первой функции с помощью бинарного поиска.

Асимптотика

Сначала оценим время вычисления каждой из функций $f_1(p)$ и $f_2(q)$ . И та, и другая содержит возведение в степень, которое можно выполнять с помощью алгоритма бинарного возведения в степень. Тогда обе этих функции мы можем вычислять за время $O(\log m)$ .

Сам алгоритм в первой фазе содержит вычисление функции $f_1(p)$ для каждого возможного значения $p$ и дальнейшую сортировку значений, что даёт нам асимптотику:

$O\left( \left\lceil \frac{m}{n} \right\rceil \lef[...]$

Во второй фазе алгоритма происходит вычисление функции $f_2(q)$ для каждого возможного значения $q$ и бинарный поиск по массиву значений $f_1$ , что даёт нам асимптотику:

$O\left( n \left( \log m + \log \left\lceil \frac{[...]$

Теперь, когда мы сложим эти две асимптотики, у нас получится $\log m$ , умноженный на сумму $n$ и $m/n$ , и практически очевидно, что минимум достигается, когда $n \approx m/n$ , т.е. для оптимальной работы алгоритма константу $n$ следует выбирать так:

$n \approx \sqrt{m}.$

Тогда асимптотика алгоритма принимает вид:

$O\left( \sqrt{m} ~ \log m \right).$

Примечание. Мы могли бы обменять ролями $f_1$ и $f_2$ (т.е. на первой фазе вычислять значения функции $f_2$ , а а второй — $f_1$ ), однако легко понять, что результат от этого не изменится, и асимптотику этим мы никак не улучшим.

Реализация

Простейшая реализация

Функция $\rm powmod$ выполняет бинарное возведение числа $a$ в степень $b$ по модулю $m$ , см. Бинарное возведение в степень.

Функция $\rm solve$ производит собственно решение задачи. Эта функция возвращает ответ (число в промежутке $[0;m)$ ), точнее говоря, один из ответов. Функция вернёт $-1$ , если решения не существует.

int powmod (int a, int b, int m) {
	int res = 1;
	while (b > 0)
		if (b & 1) {
			res = (res * a) % m;
			--b;
		}
		else {
			a = (a * a) % m;
			b >>= 1;
		}
	return res % m;
}
 
int solve (int a, int b, int m) {
	int n = (int) sqrt (m + .0) + 1;
	map<int,int> vals;
	for (int i=n; i>=1; --i)
		vals[ powmod (a, i * n, m) ] = i;
	for (int i=0; i<=n; ++i) {
		int cur = (powmod (a, i, m) * b) % m;
		if (vals.count(cur)) {
			int ans = vals[cur] * n - i;
			if (ans < m)
				return ans;
		}
	}
	return -1;
}

Здесь мы для удобства при реализации первой фазы алгоритма воспользовались структурой данных "map" (красно-чёрным деревом), которая для каждого значения функции $f_1(i)$ хранит аргумент $i$ , при котором это значение достигалось. При этом если одно и то же значение достигалось несколько раз, записывается наименьший из всех аргументов. Это сделано для того, чтобы впоследствии, на второй фазе алгоритма, нашёлся ответ в промежутке $[0;m)$ .

Учитывая, что аргумент функции $f_1()$ на первой фазе у нас перебирался от единицы и до $n$ , а аргумент функции $f_2()$ на второй фазе перебирается от нуля до $n$ , то в итоге мы покрываем всё множество возможных ответов, т.к. отрезок $[0; n^2]$ содержит в себе промежуток $[0;m)$ . При этом отрицательным ответ получиться не мог, а ответы, большие либо равные $m$ мы можем игнорировать — всё равно должны находиться соответствующие им ответы из промежутка $[0;m)$ .

Эту функцию можно изменить на тот случай, если требуется находить все решения задачи дискретного логарифма. Для этого надо заменить "map" на какую-либо другую структуру данных, позволяющую хранить для одного аргумента сразу несколько значений (например, "multimap"), и соответствующим образом изменить код второй фазы.

Улучшенная реализация

При оптимизации по скорости можно поступить следующим образом.

Во-первых, сразу бросается в глаза ненужность бинарного возведения в степень на второй фазе алгоритма. Вместо этого можно просто завести переменную и домножать её каждый раз на $a$ .

Во-вторых, таким же образом можно избавиться от бинарного возведения в степень и на первой фазе: в самом деле, достаточно один раз посчитать величину $a^n$ , и потом просто домножать на неё.

Таким образом, логарифм в асимптотике по-прежнему останется, но это будет только логарифм, связанный со структурой данных $map<>$ (т.е., в терминах алгоритма, с сортировкой и бинарным поиском значений) — т.е. это будет логарифм от $\sqrt{m}$ , что на практике даёт заметное ускорение.

int solve (int a, int b, int m) {
	int n = (int) sqrt (m + .0) + 1;
 
	int an = 1;
	for (int i=0; i<n; ++i)
		an = (an * a) % m;
 
	map<int,int> vals;
	for (int i=1, cur=an; i<=n; ++i) {
		if (!vals.count(cur))
			vals[cur] = i;
		cur = (cur * an) % m;
	}
 
	for (int i=0, cur=b; i<=n; ++i) {
		if (vals.count(cur)) {
			int ans = vals[cur] * n - i;
			if (ans < m)
				return ans;
		}
		cur = (cur * a) % m;
	}
	return -1;
}

Наконец, если модуль $m$ достаточно мал, то можно и вовсе избавиться от логарифма в асимптотике — просто заведя вместо $map<>$ обычный массив.

Также можно вспомнить про хеш-таблицы: в среднем они работают также за $O(1)$ , что в целом даёт асимптотику $O (\sqrt{m})$ .