#PQJ2675x15781. QOJ 2675_15781

    ID: 2851 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:CQTSC 2016数论

QOJ 2675_15781

一种非对称加密算法的密钥生成过程如下: 1. 任选两个不同的质数 𝑝 , 𝑞 ; 2. 计算 𝑁

𝑝 𝑞 , 𝑟

( 𝑝 − 1 ) ( 𝑞 − 1 ) ; 3. 选取小于 𝑟 ,且与 𝑟 互质的整数 𝑒 ; 4. 计算整数 𝑑 ,使得 𝑒 𝑑 ≡ 1 ( mod 𝑟 ) ; 5. 二元组 ( 𝑁 , 𝑒 ) 称为公钥,二元组 ( 𝑁 , 𝑑 ) 称为私钥。

当需要加密消息 𝑛 时(假设 𝑛 是一个小于 𝑁 的整数,因为任何格式的消息都可转为整数表示),使用公钥 ( 𝑁 , 𝑒 ) ,按照 𝑛 𝑒 ≡ 𝑐 ( mod 𝑁 ) 运算,可得到密文 𝑐 。

对密文 𝑐 解密时,用私钥 ( 𝑁 , 𝑑 ) ,按照 𝑐 𝑑 ≡ 𝑛 ( mod 𝑁 ) 运算,可得到原文 𝑛 。算法正确性证明省略。

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

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

输入格式

输入文件内容只有一行,为空格分隔的三个正整数 𝑒 , 𝑁 , 𝑐 。

输出格式

输出文件内容只有一行,为空格分隔的两个整数 𝑑 , 𝑛 。

样例数据 样例 1 输入 3 187 45 样例 1 输出 107 12 样例 1 解释

样例中 𝑝

11 , 𝑞

17 。

子任务

对于 30 % 的数据, 𝑒 , 𝑁 , 𝑐 ≤ 2 20 ;

对于 100 % 的数据, 1 ≤ 𝑒 , 𝑁 , 𝑐 ≤ 2 62 , 𝑐 < 𝑁 。