#P9589. 传信
传信
题目描述
有两个 oier 上课传纸条,他们不想被其他同学知道他们纸条的内容。于是他们决定进行 RSA 加密。
实现方法如下:
- 选择两个质数 和 ,计算 。
- 选择一个质数 ,计算 。
- 如果加密的信息为 ,那么加密后的 ,这里的 和 被称为公钥。
- 如果加密后的信息为 ,那么原信息 。
实现细节
本题是一道非传统题,你需要实现一个支持加密方式生成和解密的程序 message.cpp。
请只实现以下两个函数,不要编写 main。提交时包含 message.h,评测系统会单独链接评测库:
第一个函数是初始化函数。
void init (long long &xn, long long &xe);
请任意生成一组公钥 ,分别赋值给 和 这两个变量。
第二个函数是解密函数。
long long decrypt (long long c );
传入的参数 是加密后的信息,返回值是原信息 。
样例交互库
本地评测库与 Hydro 使用相同的函数接口。评测库从标准输入读入消息个数及全部明文,调用 init 取得公钥,再将加密后的消息传给 decrypt,逐项核对解密结果。公钥模数必须能容纳给定的明文,指数须满足题目给出的素性和逆元条件。
请下载 头文件 message.h、本地评测程序 grader.cpp、待实现模板 message.cpp 和 样例输入。
将这几个源文件放在同一目录,使用:
g++ -std=c++17 -O2 message.cpp grader.cpp -o message
不要在实现中包含 grader.cpp。你的程序可以定义辅助函数,但不得进行任何输入输出或文件操作,也不得访问评测库的私有数据。
输入第一行是消息个数 ,随后给出 个正整数明文。成功解密时,本地评测库按顺序每行打印一个明文;任何错误的公钥或解密结果都会使评测失败。
本地样例
5
6554759
76564657
8121
30525
2777735
6554759
76564657
8121
30525
2777735
子任务
| 测试点编号 | ||
|---|---|---|