e-olymp
Yarışlar

ДЛКШ-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.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3
9 187 129
11 221 56
7 391 204
Çıxış verilənləri #1
7
23
17