摘要:题目背景控诉

[THUPC2018]密码学第三次小作业

题面

题目分析

今天上午考了这道题,然而我校oj并没有把题目背景和题目描述分开(口吐芬芳),我以为是连在一起的,按照背景推了个同余方程,然后和题目描述里的方程联立求出了m,不但过了样例,回带入加密过程还都是对的,于是直接爆零…

重新来看,发现题目中e1和e2互素,于是有:

$pe_1+qe_2 =1 $

根据扩展欧几里得定理,以上不定方程一定有解,而且容易看出p和q一定为一正一负,这里取q为负.

然后我们有:

$m \equiv m^1 \equiv m^{pe_1+qe_2} (mod ~ N)$

又因为有:

$m^{e_1} ~ mod ~ N = c_1$

$m^{e_2} ~ mod ~ N = c_2$

所以原式变为:

$m \equiv c_1^pc_2^q ~ (mod ~ N)$

p和q前面已经通过exgcd求出,不过需要注意的是q为负数,没法计算.

考虑转化一下,因为是在模N的意义下,很明显有:

$(c_2^{-1})^{-q}=c_2^q ~ (mod ~ N)$

所以求出c2的逆元就可以计算了.

提醒一下快速幂里打龟速乘,不然第二个点爆long long.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cstdlib"
#include "cmath"
#include "cctype"
#include "iomanip"
#include "algorithm"
#include "time.h"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "vector"
#include "deque"
#define lxl long long
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
lxl T,c1,c2,e1,e2,n;
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f*x;
}
lxl exGCD(lxl a,lxl b,lxl &x,lxl &y)
{
if(!b){x=1,y=0;return a;}
lxl tmp=exGCD(b,a%b,x,y),t=x;
x=y,y=t-a/b*y;
return tmp;
}
inline lxl FastMul(lxl a,lxl b,lxl mod)
{
lxl sum=0;
for(;b;b>>=1,a=(a+a)%mod)(b&1)&&(sum=(sum+a)%mod);
return sum;
}
inline lxl FastPow(lxl a,lxl b,lxl mod)
{
lxl sum=1;
for(;b;b>>=1,a=FastMul(a,a,mod))(b&1)&&(sum=FastMul(sum,a,mod));
return sum;
}
int main(void)
{
T=read();
while(T--)
{
c1=read(),c2=read(),e1=read(),e2=read(),n=read();
lxl p,q;
exGCD(e1,e2,p,q);
p%=e2,q%=e1;
while(p<0)p+=e2;
while(q>0)q-=e1;
lxl inv,y;
exGCD(c2,n,inv,y);
inv=(inv%n+n)%n;
q*=-1;
printf("%lld\n",FastMul(FastPow(c1,p,n),FastPow(inv,q,n),n));
}
return 0;
}