#P9589. 传信

    ID: 6206 传统题 2000ms 512MiB 尝试: 2 已通过: 1 难度: 4 上传者: 标签>难度分类普及+/提高-数论欧拉函数模逆元扩展欧几里得算法快速幂快速乘防溢出费马小定理CF1600乘法逆元

传信

题目描述

有两个 oier 上课传纸条,他们不想被其他同学知道他们纸条的内容。于是他们决定进行 RSA 加密。

实现方法如下:

  1. 选择两个质数 pp 和 qq,计算 n=p×qn=p\times q。
  2. 选择一个质数 e<φ(n)e<\varphi(n),计算 d=e−1 mod φ(n)d=e^{-1}\bmod \varphi(n)。
  3. 如果加密的信息为 mm,那么加密后的 c=me mod nc=m^e\bmod n,这里的 ee 和 nn 被称为公钥。
  4. 如果加密后的信息为 cc,那么原信息 m=cd mod nm=c^d\bmod n。

实现细节

本题是一道非传统题,你需要实现一个支持加密方式生成和解密的程序 message.cpp。

请只实现以下两个函数,不要编写 main。提交时包含 message.h,评测系统会单独链接评测库:

第一个函数是初始化函数。

void init (long long &xn, long long &xe);

请任意生成一组公钥 (n,e)(n,e),分别赋值给 xnxn 和 xexe 这两个变量。

第二个函数是解密函数。

long long decrypt (long long c );

传入的参数 cc 是加密后的信息,返回值是原信息 mm。

样例交互库

本地评测库与 Hydro 使用相同的函数接口。评测库从标准输入读入消息个数及全部明文,调用 init 取得公钥,再将加密后的消息传给 decrypt,逐项核对解密结果。公钥模数必须能容纳给定的明文,指数须满足题目给出的素性和逆元条件。

请下载 头文件 message.h、本地评测程序 grader.cpp、待实现模板 message.cpp 和 样例输入。

将这几个源文件放在同一目录,使用:

g++ -std=c++17 -O2 message.cpp grader.cpp -o message

不要在实现中包含 grader.cpp。你的程序可以定义辅助函数,但不得进行任何输入输出或文件操作,也不得访问评测库的私有数据。

输入第一行是消息个数 tt,随后给出 tt 个正整数明文。成功解密时,本地评测库按顺序每行打印一个明文;任何错误的公钥或解密结果都会使评测失败。

本地样例

5
6554759
76564657
8121
30525
2777735
6554759
76564657
8121
30525
2777735

子任务

测试点编号 nn aia_i
1,2,31,2,3 ≤500\leq 500 ≤103\leq 10^3
4,5,64,5,6 ≤8×103\leq 8\times 10^3 ≤105\leq 10^5
7,8,9,107,8,9,10 ≤1018\leq 10^{18}