Атака на RSA
Проблема RSA полягає в наступному: дано натуральне число n, яке є добутком двох різних простих непарних чисел p та q, натуральне e таке що НСД(e, (p−1)·(q−1)) = 1, а також ціле c. Необхідно знайти таке натуральне m, що me = 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 секундаЛіміт пам`яті: 64 MB
Бали за пройдений тест: 20
Складність: 18% 14/17
Приклад
Приклад вхідних даних3 9 187 129 11 221 56 7 391 204 |
Приклад вихідних даних7 23 17 |
| ← Число що зменшується | Список задач | Модулярні рівняння → |