Ключ от RSA

Сердце RSA - обратный элемент по модулю: для чисел a и m найдите такое x (0 <= x < m), что (a * x) mod m == 1, или верните -1, если x не существует (a и m не взаимно просты). Перебор до m сработает на тестах, но красивое решение - расширенный алгоритм Евклида.