Атака на 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 |
| ← Уменьшающееся число | Список задач | Модулярные уравнения → |