eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Атака на RSA

Атака на RSA

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Проблема RSA полягає в наступному: дано натуральне число n, яке є добутком двох різних простих непарних чисел p та q, натуральне e таке що НСД(e, (p−1)·(q−1)) = 1, а також ціле c. Необхідно знайти таке натуральне m, що m^e = 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
3
9 187 129
11 221 56
7 391 204
Вихідні дані #1
7
23
17