TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3614
  • 题目
  • P3614【CQOI2016 Day2】密钥破解
    限制 : 时间限制 : 10000 MS   空间限制 : 524288 KB
    问题描述

            一种非对称加密算法的密钥生成过程如下:
                    1.任选两个不同的质数p,q;
                    2.计算N=pq,r=(p-1)(q-1);
                    3.选取小于r,且与r互质的整数e;
                    4.计算整数d,使得ed≡1 mod r;
                    5.二元组(N,e)称为公钥,二元组(N,d)称为私钥。
            当需要加密消息n时(假设n是一个小于N的整数,因为任何格式的消息都可以转为整数表示),使用公钥(N,e),按照

    ne≡c mod N

    运算,可以得到密文c。
            对密文解密时,用私钥(N,d),按照
    cd≡n mod N

    运算,可以得到原文n。算法正确性证明省略。
            由于公钥加密的密文仅能用对应的私钥解密,而不能用公钥解密,因此称为非对称加密算法。通常情况下,公钥有消息的接收方公开,而私钥由消息的接收方自己持有。这样任何发消息的人都可以用公钥对消息加密,而只有消息的接收方自己能够解密消息。
            现在,你的任务是寻找一种可行的方法来破解这种加密算法,即根据公钥破接出私钥,并据此解密密文。

    输入格式

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

    输出格式

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

    样例输入

    3 187 45

    样例输出

    107 12

    提示

    样例解释:
            样例中p=11,q=17。

    数据范围:
            对于30%的测试数据,N≤106
            对于50%的测试数据,N≤1014
            对于100%的测试数据,N≤262


    来源  感谢nodgd研究了很久如何排版比较美观