4074: 「CQOI2016」密钥破解

一种非对称加密算法的密钥生成过程如下： 1. 任选两个不同的质数 $p, q$； 2. 计算 $N = pq, r=(p-1)(q-1)$； 3. 选取小于 $r$，且与 $r$ 互质的整数 $e$； 4. 计算整数 $d$，使得 $ed \equiv 1 \pmod r$； 5. 二元组 $(N, e)$ 称为**公钥**，二元组 $(N, d)$ 称为**私钥**。 当需要加密消息 $n$ 时（假设 $n$ 是一个小于 $N$ 的整数，因为任何格式的消息都可转为整数表示），使用公钥 $(N, e)$，按照 $$n^e \equiv c \pmod N$$ 运算，可得到密文 $c$。 对密文 $c$ 解密时，用私钥 $(N, d)$，按照 $$c^d \equiv n \pmod N$$ 运算，可得到原文 $n$。算法正确性证明省略。 由于用公钥加密的密文仅能用对应的私钥解密，而不能用公钥解密，因此称为非对称加密算法。通常情况下，公钥由消息的接收方公开，而私钥由消息的接收方自己持有。这样任何发送消息的人都可以用公钥对消息加密，而只有消息的接收方自己能够解密消息。 现在，你的任务是寻找一种可行的方法来破解这种加密算法，即根据公钥破解出私钥，并据此解密密文。

输入文件内容只有一行，为空格分隔的三个正整数 $e, N, c$。

输出文件内容只有一行，为空格分隔的两个整数 $d, n$。

3 187 45

107 12