P1601 - [ECUST2018新生赛]破解密码

内存限制：256 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：203 通过：46

RSA算法是一种公钥加密算法，RSA算法相比别的算法思路非常清晰，但是想要破解的难度非常大。
RSA算法基于一个非常简单的数论事实：两个素数相乘得到一个大数很容易，但是由一个大数分解为两个素数相乘却非常难。
RSA基于三个参数进行加密和解密的操作，分别是n,pub,pri, 这里(n,pub)称为公钥，(n,pri)称为秘钥。
n是两个不同素数p和q的乘积，由数论知识可知n的欧拉函数φ(n)=(p-1)(q-1)，pub与φ(n)互质，pri是pub关于φ(n)的逆元。
公钥可以将明文加密成密文，秘钥则可以将密文解密成明文。所以只要得到秘钥就可以破解密码啦。
小花梨最近学了这个RSA算法，想考考小信息的计算能力，它只告诉小信息公钥(n,pub)，希望它能破解出秘钥
但是小信息完全不知所措，所以小花梨只能告诉小信息具体的破解方案：
首先算出n的素因子p和q，那么就可以算出φ(n)，根据pub和pri关于φ(n)互为逆元，就可以直接算出秘钥pri啦。
为了让小信息更加容易破解密码，以及减少小信息的计算量，
给出的n是相邻的两个素数p和q的乘积，而且不需要小信息求出φ(n)以及pri，只需要求出p+q的值就算解密成功啦。
小信息来向你求助，你能帮帮它吗？

第一行一个整数T，表示有T组数据(1≤T≤1000)
对于每组数据，输入一行，只有一个整数n(6≤n≤10^18)
输入保证n=p∗q,2≤p,q≤10^9

对于每一组数据，输出"Case x: ans"(不含引号)
x表示第x组测试数据，从1开始编号，ans表示p+q的值

Case 1: 5
Case 2: 18
Case 3: 30
Case 4: 186

第1-4组的p和q分别为：2,3、7,11、13,17、89,97
注：在现实生活加密过程中，n将会达到2000位以上，这样的话破解起来是非常困难的，从而保证了加密的安全性。

EFPC

1601: [ECUST2018新生赛]破解密码

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签