Головна |
Завдання дискретного логарифмування полягає в тому, щоб за даними цілим , , вирішити рівняння:
де и - Взаємно прості
int solve (int a, int b, int m) {
int n = (int) sqrt (m + .0) + 1;
int an = 1;
for (int i = 0; i an = (an * a)% m; map 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 return ans; } cur = (cur * a)% m; } return -1; } Розширений Евклід | Теорема Піка.
Флойд-Уоршелл | Алгоритм пошуку компонент зв'язності в графі | Пошук точок зчленування | Алгоритм Куна знаходження найбільшого паросполучення в дводольному графі | Z-функція рядка і її обчислення | Знаходження наідліннейшей зростаючої підпослідовності | Знаходження найбільшою нульовий подматріци | Біноміальні коефіцієнти | числа Каталана | намиста |