#2045. 「CQOI2016」密钥破解

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

一种非对称加密算法的密钥生成过程如下:

  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

样例解释

样例中 p = 11, q = 17

数据范围与提示

对于 30\% 的数据, e, N, c \leq 2^{20}
对于 100\% 的数据, 1 \leq e, N, c \leq 2^{62}, c < N