e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

ДЛКШ-2011 Теорія чисел. Вибране

Атака на RSA

Проблема RSA полягає в наступному: дано натуральне число n, яке є добутком двох різних простих непарних чисел p та q, натуральне e таке що НСД(e, (p−1)·(q−1)) = 1, а також ціле c. Необхідно знайти таке натуральне m, що me = c (mod n).

Вхідні дані

Перший рядок містить кількість тестів k (k2000). Кожний наступний рядок є окремим тестом і містить три числа e, n та c (e, n, c32000, n = p · q; p, q — різні непарні прості числа, НСД(e, (p−1)·(q−1)) = 1, e < (p − 1)·(q − 1)).

Вихідні дані

Для кожного тесту в окремому рядку надрукувати значення m.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
9 187 129
11 221 56
7 391 204
Вихідні дані #1
7
23
17