MAXimal | |
добавлено: 10 Jun 2008 18:08 Содержание [скрыть] Дискретное логарифмированиеЗадача дискретного логарифмирования заключается в том, чтобы по данным целым где Здесь описан алгоритм, известный как "baby-step-giant-step algorithm", предложенный Шэнксом (Shanks) в 1971 г., работающий за время за АлгоритмИтак, мы имеем уравнение: где Преобразуем уравнение. Положим где Очевидно, что любое Тогда уравнение принимает вид: откуда, пользуясь тем, что Чтобы решить исходное уравнение, нужно найти соответствующие значения Эта задача решается с помощью метода meet-in-the-middle следующим образом. Первая фаза алгоритма: посчитаем значения функции АсимптотикаСначала оценим время вычисления каждой из функций Сам алгоритм в первой фазе содержит вычисление функции Во второй фазе алгоритма происходит вычисление функции Теперь, когда мы сложим эти две асимптотики, у нас получится Тогда асимптотика алгоритма принимает вид: Примечание. Мы могли бы обменять ролями РеализацияПростейшая реализацияФункция Функция 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" (красно-чёрным деревом), которая для каждого значения функции Учитывая, что аргумент функции Эту функцию можно изменить на тот случай, если требуется находить все решения задачи дискретного логарифма. Для этого надо заменить "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; } Наконец, если модуль Также можно вспомнить про хеш-таблицы: в среднем они работают также за
|