1275: #2045. 「CQOI2016」密钥破解

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

  1. 任选两个不同的质数 p,qp, qp,q
  2. 计算 N=pq,r=(p−1)(q−1)N = pq, r=(p-1)(q-1)N=pq,r=(p1)(q1)
  3. 选取小于 rrr,且与 rrr 互质的整数 eee
  4. 计算整数 ddd,使得 ed1(modr)
  5. 二元组 (N,e)(N, e)(N,e) 称为公钥,二元组 (N,d)(N, d)(N,d) 称为私钥

当需要加密消息 nnn 时(假设 nnn 是一个小于 NNN 的整数,因为任何格式的消息都可转为整数表示),使用公钥 (N,e)(N, e)(N,e),按照

nec(modN)

运算,可得到密文 ccc

对密文 ccc 解密时,用私钥 (N,d)(N, d)(N,d),按照

cdn(modN)

运算,可得到原文 nnn。算法正确性证明省略。

由于用公钥加密的密文仅能用对应的私钥解密,而不能用公钥解密,因此称为非对称加密算法。通常情况下,公钥由消息的接收方公开,而私钥由消息的接收方自己持有。这样任何发送消息的人都可以用公钥对消息加密,而只有消息的接收方自己能够解密消息。

现在,你的任务是寻找一种可行的方法来破解这种加密算法,即根据公钥破解出私钥,并据此解密密文。

输入格式

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

输出格式

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

样例

样例输入

3 187 45

样例输出

107 12

样例解释

样例中 p=11,q=17p = 11, q = 17p=11,q=17

数据范围与提示

对于 30%30\%30% 的数据,e,N,c≤220e, N, c \leq 2^{20}e,N,c220
对于 100%100\%100% 的数据,1≤e,N,c≤262,c<N1 \leq e, N, c \leq 2^{62}, c < N1e,N,c262,c<N