e-maxx_algo

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

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

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

Здесь описан алгоритм, известный как "baby-step-giant-step algorithm", предложенный Шэнксом (Shanks) в 1971 г., работающий за время за . Часто этот алгоритм просто

называют алгоритмом "meet-in-the-middle" (потому что это одно из классических применений техники "meet-in- the-middle": "разделение задачи пополам").

Алгоритм

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

где и взаимно просты. Преобразуем уравнение. Положим

где — это заранее выбранная константа (как её выбирать в зависимости от , мы поймём чуть позже). Иногда

называют "giant step" (поскольку увеличение его на единицу увеличивает сразу на ), а в противоположность ему

— "baby step".

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

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

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

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

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

алгоритма: будем перебирать значение второй переменной , вычислять вторую функцию , и искать это значение среди предвычисленных значений первой функции с помощью бинарного поиска.

Асимптотика

Сначала оценим время вычисления каждой из функций и . И та, и другая содержит возведение в степень, которое можно выполнять с помощью алгоритма бинарного возведения в степень. Тогда обе этих функции мы можем вычислять за время .

дальнейшую сортировку значений, что даёт нам асимптотику:

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

— ), однако легко понять, что результат от этого не изменится, и асимптотику этим мы никак не улучшим.

Реализация

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

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" (красно-чёрным деревом), которая для каждого значения функции хранит аргумент , при котором

это значение достигалось. При этом если одно и то же значение достигалось несколько раз, записывается наименьший из всех аргументов. Это сделано для того, чтобы впоследствии, на второй фазе алгоритма, нашёлся ответ в промежутке .

на второй фазе перебирается от нуля до , то в итоге мы покрываем всё множество возможных ответов, т.к.

ответы, большие либо равные мы можем игнорировать — всё равно должны находиться соответствующие им ответы из промежутка .

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

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

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

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

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

Таким образом, логарифм в асимптотике по-прежнему останется, но это будет только логарифм, связанный со структурой данных (т.е., в терминах алгоритма, с сортировкой и бинарным поиском значений) — т.е. это будет логарифм от , что на практике даёт заметное ускорение.

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;

}

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

Линейные диофантовы уравнения с двумя переменными

Диофантово уравнение с двумя неизвестными имеет вид:

где — заданные целые числа, и — неизвестные целые числа.

Ниже рассматриваются несколько классических задач на эти уравнения: нахождение любого решения, получение всех решений, нахождение количества решений и сами решения в определённом отрезке, нахождение решения с наименьшей суммой неизвестных.

Вырожденный случай

Один вырожденный случай мы сразу исключим из рассмотрения: когда . В этом случае, понятно, уравнение имеет либо бесконечно много произвольных решений, либо же не имеет решений вовсе (в зависимости от того, или нет).

Нахождение одного решения

Найти одно из решений диофантова уравнения с двумя неизвестными можно с помощью Расширенного алгоритма Евклида. Предположим сначала, что числа и неотрицательны.

Расширенный алгоритм Евклида по заданным неотрицательным числам и находит их наибольший общий делитель

в противном случае диофантово уравнение решений не имеет. Доказательство следует из очевидного факта, что линейная комбинация двух чисел по-прежнему должна делиться на их общий делитель.

Предположим, что делится на , тогда, очевидно, выполняется:

т.е. одним из решений диофантова уравнения являются числа:

Мы описали решение в случае, когда числа и неотрицательны. Если же одно из них или они оба отрицательны, то можно поступить таким образом: взять их по модулю и применить к ним алгоритм Евклида, как было описано выше, а затем изменить знак найденных и в соответствии с настоящим знаком чисел и соответственно.

Реализация (напомним, здесь мы считаем, что входные данные недопустимы):

int gcd (int a, int b, int & x, int & y) { if (a == 0) {

x = 0; y = 1; return b;

}

int x1, y1;

int d = gcd (b%a, a, x1, y1); x = y1 - (b / a) * x1;

y = x1; return d;

}

bool find_any_solution (int a, int b, int c, int & x0, int & y0, int & g) { g = gcd (abs(a), abs(b), x0, y0);

if (c % g != 0)

return false; x0 *= c / g;

y0 *= c / g;

}

Получение всех решений

Покажем, как получить все остальные решения (а их бесконечное множество) диофантова уравнения, зная одно из решений .

Итак, пусть , а числа удовлетворяют условию:

Тогда заметим, что, прибавив к число и одновременно отняв от , мы не нарушим равенства:

Очевидно, что этот процесс можно повторять сколько угодно, т.е. все числа вида:

являются решениями диофантова уравнения.

Более того, только числа такого вида и являются решениями, т.е. мы описали множество всех решений диофантова уравнения (оно получилось бесконечным, если не наложено дополнительных условий).

Нахождение количества решений и сами решения в заданном отрезке

Приведём реализацию (она получилась достаточно сложной, поскольку требуется аккуратно рассматривать случаи положительных и отрицательных коэффициентов и ):

void shift_solution (int & x, int & y, int a, int b, int cnt) { x += cnt * b;

y -= cnt * a;

}

int find_all_solutions (int a, int b, int c, int minx, int maxx, int miny, int maxy) {

int x, y, g;

if (! find_any_solution (a, b, c, x, y, g)) return 0;

a /= g; b /= g;

int sign_a = a>0 ? +1 : -1; int sign_b = b>0 ? +1 : -1;

shift_solution (x, y, a, b, (minx - x) / b); if (x < minx)

shift_solution (x, y, a, b, sign_b); if (x > maxx)

return 0; int lx1 = x;

shift_solution (x, y, a, b, (maxx - x) / b); if (x > maxx)

shift_solution (x, y, a, b, -sign_b); int rx1 = x;

shift_solution (x, y, a, b, - (miny - y) / a); if (y < miny)

shift_solution (x, y, a, b, -sign_a); if (y > maxy)

return 0; int lx2 = x;

shift_solution (x, y, a, b, - (maxy - y) / a); if (y > maxy)

shift_solution (x, y, a, b, sign_a); int rx2 = x;

if (lx2 > rx2)

swap (lx2, rx2); int lx = max (lx1, lx2); int rx = min (rx1, rx2);

return (rx - lx) / abs(b) + 1;

}

Также нетрудно добавить к этой реализации вывод всех найденных решений: для этого достаточно перебрать в

Нахождение решения в заданном отрезке с наименьшей суммой x+y

Здесь на и на также должны быть наложены какие-либо ограничения, иначе ответом практически всегда будет минус бесконечность.

Идея решения такая же, как и в предыдущем пункте: сначала находим любое решение диофантова уравнения, а затем, применяя описанную в предыдущем пункте процедуру, придём к наилучшему решению.

Действительно, мы имеем право выполнить следующее преобразование (см. предыдущий пункт):

Заметим, что при этом сумма меняется следующим образом:

Если , то мы никак не сможем улучшить решение, — все решения будут обладать одной и той же суммой.

Задачи в online judges

Список задач, которые можно сдать на тему диофантовых уравнений с двумя неизвестными: ● SGU #106 "The Equation" [сложность: средняя]

Модульное линейное уравнение первого порядка

Постановка задачи

Это уравнение вида:

где — заданные целые числа, — неизвестное целое число.

Решение с помощью нахождения Обратного элемента

Рассмотрим сначала более простой случай — когда и взаимно просты. Тогда можно найти обратный элемент к числу , и, домножив на него обе части уравнения, получить решение (и оно будет единственным):

Теперь рассмотрим случай, когда и не взаимно просты. Тогда, очевидно, решение будет существовать не всегда (например, ).

не единственным решением. Можно показать, что исходное уравнение будет иметь ровно решений, и они будут иметь вид:

Подводя итог, можно сказать, что количество решений линейного модульного уравнения равно либо , либо нулю.

Решение с помощью Расширенного алгоритма Евклида

Приведём наше модулярное уравнение к диофантову уравнению следующим образом:

где и — неизвестные целые числа.

Способ решения этого уравнения описан в соответствующей статье Линейные диофантовы уравнения второго порядка, и заключается он в применении Расширенного алгоритма Евклида.

Там же описан и способ получения всех решений этого уравнения по одному найденному решению, и, кстати говоря, этот способ при внимательном рассмотрении абсолютно эквивалентен способу, описанному в предыдущем пункте.

Алгоритм Гарнера

Из китайской теоремы об остатках следует, что можно заменять операции над числами операциями над кортежами. Напомним, каждому числу ставится в соответствие кортеж , где:

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

Алгоритм Гарнера и является алгоритмом, позволяющим выполнить это восстановление, причём достаточно эффективно.

Будем искать решение в виде:

т.е. в смешанной системе счисления с весами разрядов .

Подставим выражение в смешанной системе счисления в первое уравнение системы, получим:

Подставим теперь выражение во второе уравнение:

Преобразуем это выражение, отняв от обеих частей и разделив на :

Подставляя в третье уравнение, аналогичным образом получаем:

Уже достаточно ясно видна закономерность, которую проще всего выразить кодом:

for (int i=0; i<k; ++i) { x[i] = a[i];

for (int j=0; j<i; ++j) {

x[i] = r[j][i] * (x[i] - x[j]);

x[i] = x[i] % p[i];

if (x[i] < 0) x[i] += p[i];

}

}

Стоит заметить, что на практике почти всегда вычислять ответ нужно с помощью Длинной арифметики, но при этом

сами коэффициенты по-прежнему вычисляются на встроенных типах, а потому весь алгоритм Гарнера является весьма эффективным.