题目
题目背景
Diffie-Hellman密钥交换协议是一种简单有效的密钥交换方法。它可以让通讯双方在没有事先约定密钥(密码) 的情况下，通过不安全的信道(可能被窃听) 建立一个安全的密钥K,用于加密之后的通讯内容。
题目描述
假定通讯双方名为Alice和Bob,协议的工作过程描述如下(其中 mod 表示取模运算) :
协议规定一个固定的质数P,以及模P 的一个原根g。P 和g 的数值都是公开的，无需保密。
Alice 生成一个随机数a,并计算A=g^a;mod;PA=g
a
modP, 将A 通过不安全信道发送给Bob。
Bob 生成一个随机数b,并计算B=g^b;mod;PB=g
b
modP,将B 通过不安全信道发送给Alice。
Bob 根据收到的A 计算出K=A^b;mod;PK=A
b
modP,而Alice 根据收到的B 计算出K=B^a;mod;PK=B
a
modP。
双方得到了相同的K,即g^{ab};mod;Pg
ab
modP。K 可以用于之后通讯的加密密钥。
可见，这个过程中可能被窃听的只有A、B,而a、b、K 是保密的。并且根据A、B、P、g 这4个数,不能轻易计算出K,因此K 可以作为一个安全的密钥。
当然安全是相对的，该协议的安全性取决于数值的大小，通常a、b、P 都选取数百位以上的大整数以避免被破解。然而如果Alice 和Bob 编程时偷懒，为了避免实现大数运算,选择的数值都小于2^{31}2
31
,那么破解他们的密钥就比较容易了。
输入格式
输入文件第一行包含两个空格分开的正整数g 和P。
第二行为一个正整数n, 表示Alice 和Bob 共进行了n 次连接(即运行了n 次协议)。
接下来n 行，每行包含两个空格分开的正整数A 和B，表示某次连接中，被窃听的A、B 数值。
输出格式
输出包含n 行，每行1个正整数K,为每次连接你破解得到的密钥。
输入输出样例
输入 #1复制
3 31
3
27 16
21 3
9 26
输出 #1复制
4
21
25
说明/提示
对于30%的数据，2≤A,B,P≤10002≤A,B,P≤1000
对于100%的数据，2≤A,B<P<2^{31},2≤g<20,1≤n≤202≤A,B<P<2
31
,2≤g<20,1≤n≤20
思路
BSGS算法(Baby Step Giant Step)，即大步小步算法，用于求解这样的问题
yx≡ z(mod p) 的最小整数解，前提条件 （y,p）=1。
此时先计算出m = sqrt§
然后另 x = im+j,此时有i,j<m
移项有 ymi ≡z*y-j,因为有逆元，不爽
重新另x = im-j,这样移项是就能不去算逆元了
这时有 ymi ≡ z*yj .
这时只用枚举
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll g,p,a,b,m;
int n;
map<ll,int> t;
ll power(ll x,ll t)
{
ll ans=1;for(;t;t>>=1,x=x*x%p)if(t&1) ans=ans*x%p;return ans;
}
ll calc(int x)
{
ll nowx=x;if(t[nowx]) return t[nowx];for(int i=1;i<m;i++){
nowx=nowx*g%p;if(t[nowx]) return t[nowx]-i;}
}
void init()
{
m=sqrt(p)+1;ll powx=power(g,m);ll nowx=1;for(int i=1;i<=m;i++){
nowx=nowx*powx%p;t[nowx]=i*m; }
}
int main()
{
scanf("%lld%lld",&g,&p);init();scanf("%d",&n);while(n--){
scanf("%lld%lld",&a,&b);printf("%lld\n",power(b,calc(a)));}
}