加密通话
题目背景
如果您急于 AK
后过元旦,请直接看简化题面。
“哔哔啵啵…哔哔哔……啵~”此起彼伏的电报声在机房回响(不要问为什么会有电报。)。
啊,$\text{RenaMoe}$ 在通信!
显示器上蓝灯、绿灯、红灯,你不让我,我不让你,都闪满了灯赶趟儿。红的像火,绿的像草,蓝的像天。灯里带着迷影,闭了眼,显示屏上仿佛已经满是灯儿、字儿、$OIer$(——改变自老舍的《春》)。
嗯?上面的字怎么读不通?
$\text{RenaMoe}$:因为我们用了加密通话!
哇,这也太厉害了!那您怎么知道对方发的信息是什么意思呢?
$\text{RenaMoe}$:是这样的,首先我会先和对方预定好一个模数 $p$,和模 $p$ 的一个原根 $g$(当成一个数就行)。
$\text{RenaMoe}$:然后我将我的信息编辑成数字信息 $x$,然后向他发送加密后的信息 $R$,其中 $R=g^x\mod p$。
$\text{RenaMoe}$:接着我会接受对方回复的信息 $L$,同样 $L=g^y\mod p$,$y$ 就是对方回复的信息。
$\text{RenaMoe}$: 接着我会将 $y$ 求出,然后计算 $M=R^y\mod p$ 作为下一次通信的加密密钥。同样,对方会计算 $M=L^x\mod p$。
$\text{RenaMoe}$:因为我们得到的答案都是:$M=g^{xy}\mod p$ 所以我们都可以得到下一次通讯加密密钥。
哇,这太聪明了!
$\text{RenaMoe}$:但是,这种方式并不能有效的保证通讯秘密。由于我们的通话信息可以被同一个人读取,也就是说你可以同时知道 $L,R$,如果你还知道我们提前预设的 $g$ 和 $p$。
$\text{RenaMoe}$:然后你可通过这个可以计算出 $M$ 就可以知道我们下一次的通话信息呢!
真的么?那要怎么做呢?
$\text{RenaMoe}$:“$@!##*!…#%!@#$”(加密交流)。
奥,那我现在就试试!
$\text{RenaMoe}$:(\托腮)。
解析完毕:$\text{RenaMoe}$:我今天中午想吃 $banana$,你可以帮我带亿点点吗?
简化题面
现在有 $L=g^y\mod p,R=g^x\mod p$,请求出 $M=g^{xy}\mod p$。
输入
第一行两个数 $g$ 和 $p$。
第二行一个数 $n$。
后面有 $n$ 行,每行两个数:$L,R$。
输出
输出 $n$ 行,代表每次破解的 $M$。
样例 $1$
读入
11 23
2
4 7
1 20
输出
8
1
样例 $2$
读入
50 59
3
26 13
12 14
14 15
输出
25
7
5
样例 $3$
读入
31 71
5
62 30
12 54
43 37
65 57
37 47
输出
45
57
32
54
45
样例 $4$
读入
2780303 9613367
3
8199460 8916560
9376676 3921108
2576481 4520467
输出
8302437
8872205
5937276
数据范围
- $10\%:$
$1 \le n \le 10$
$2\le L,R < P < 1e3$
- $30\%:$
$1 \le n \le 20$
$2\le L,R < P < 1e8$
- 另 $10\%:$
$2\le L=R < P < 1e8$
- $100\%:$
$1 \le n \le 200$
$2\le L,R < P < 1e8$
对于各个范围内的 $g$ 保证一定存在且是原根。$p$ 一定是一个质数。
题解
本题是一个 BSGS
的板子题。
通过 BSGS
求出 $y$。
计算 $M\mod p$ 输出即可。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<string>
#include<cmath>
#include<map>
#include<vector>
using namespace std;
long long r_r(){
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
map<long long,long long>h_h;
long long k_m(long long a,long long b,long long m_d){//快速幂
long long r_s=1;
while(b){
if(b&1)r_s=(r_s*a)%m_d;
a=(a*a)%m_d;
b>>=1;
}
return r_s;
}
long long b_g(long long a,long long b,long long m_d){//BSGS
h_h.clear();
int s_z=ceil(sqrt(m_d));
long long b_s=b%m_d;
h_h[b_s]=0;
for(int i=1;i<=s_z;i++){
b_s=b_s*a%m_d;
h_h[b_s]=i;
}
b_s=k_m(a,s_z,m_d);
long long t_p=1;
for(long long i=1;i<=s_z;i++){
t_p=t_p*b_s%m_d;
if(h_h[t_p])
return((i*s_z-h_h[t_p])%m_d+m_d)%m_d;
}
return-1;
}
int main(){
long long g=r_r(),m_d=r_r();
long long n=r_r();
while(n--){
long long a_i=r_r(),b_i=r_r();//读取每次的 L,R
long long k=b_g(g,a_i,m_d);//通过其中一个计算 x 或了另一个计算 y
printf("%lld\n",k_m(b_i,k,m_d));//计算 M
}
return 0;
}