На головну

дискретного логарифмування

Завдання дискретного логарифмування полягає в тому, щоб за даними цілим , ,  вирішити рівняння:

де и  - Взаємно прості

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 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

return ans;

}

cur = (cur * a)% m;

}

return -1;

}

 



Розширений Евклід | Теорема Піка.

Флойд-Уоршелл | Алгоритм пошуку компонент зв'язності в графі | Пошук точок зчленування | Алгоритм Куна знаходження найбільшого паросполучення в дводольному графі | Z-функція рядка і її обчислення | Знаходження наідліннейшей зростаючої підпослідовності | Знаходження найбільшою нульовий подматріци | Біноміальні коефіцієнти | числа Каталана | намиста |

© um.co.ua - учбові матеріали та реферати