Задачі
Атака на RSA
Атака на RSA
Проблема RSA полягає в наступному: дано натуральне число n, яке є добутком двох різних простих непарних чисел p та q, натуральне e таке що НСД(e, (p−1)·(q−1)) = 1, а також ціле c. Необхідно знайти таке натуральне m, що m^e = c (mod n).
Вхідні дані
Перший рядок містить кількість тестів k (k ≤ 2000). Кожний наступний рядок є окремим тестом і містить три числа e, n та c (e, n, c ≤ 32000, 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