跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0158. #2045. 「CQOI2016」密钥破解

  • ID: 164
  • 传统题
  • 1000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 数论
  • 数学
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

#2045. 「CQOI2016」密钥破解

题目描述

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

  1. 任选两个不同的质数 ;
  2. 计算 ;
  3. 选取小于 ,且与 互质的整数 ;
  4. 计算整数 ,使得 ed≡1(modr);
  5. 二元组 称为公钥,二元组 称为私钥。

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

ne≡c(modN)

运算,可得到密文 。

对密文 解密时,用私钥 ,按照

cd≡n(modN)

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

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

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

输入格式

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

输出格式

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

样例

样例输入

3 187 45

样例输出

107 12

样例解释

样例中 。

数据范围与提示

对于 的数据,;
对于 的数据,。


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 41 题。保留原作者与原赛事署名。