[SHUOJ423] 密码破解 2017上海金马五校赛 N 题

题目

题目链接
题目大意为给你一串加密的数字,要求你解密。加密的原则为 b \equiv a^e \ (Mod\ m) 其中 m\ =\ p\ *\ q, p,q 是两个不相同的质数。并且给你一些公式。
 

解题思路

根据题目公式得存在一个 d 使得 a = b^d\%m 那么题目则变为求 d.
b^d\ \equiv\ (a^e)^d\ \equiv\ a\ (Mod\ m)a^{ed}\ \equiv\ a^{1}\ (Mod\ m).
有欧拉定理得 ed\ \equiv\ 1\ (Mod\ \phi(m)) 其中 \phi(m)\ =\ (p-1)*(q-1)
因为题目保证有解,则可以用扩展欧几里得求出 d, 在用快速幂求出加密之前的序列。因为数据较大,在快速幂中要使用按位相乘(比赛时没加导致最后这题没过😟😟😟😟)。
 

代码

 

完结

shuoj423

发表评论

电子邮件地址不会被公开。 必填项已用*标注