hdu 1211 RSA (扩展欧几里得算法求逆元 +快速幂)

题目链接

题意:给出p, q, e, l,令n = p * q, fn = (p-1) * (q-1)

给出l个c,计算m = D(c) = cd mod n,其中m为要输入的明文对应的ascii编码,d的计算方法:> calculate d, making d × e mod F(n) = 1 mod F(n), and d will be the private key。

问明文。

 

思路:

出题人JGShining(极光炫影)傻逼。

题意都说不清?

大小写字母一个意思?

脑袋有坑的出题人。

出题人傻逼。

出题人傻逼。

出题人傻逼。

 

 

好了。这道题需要用到扩展欧几里得算法求逆元。。。ksm(a,mod-2)的方法是基于费马小定理,必须mod为质数才可以用。扩展偶记里算法没有这个限制。

用欧几里德算法求模的逆元:

同余方程ax≡b (mod n),如果 gcd(a,n)== 1,则方程只有唯一解。

在这种情况下,如果 b== 1,同余方程就是 ax=1 (mod n ),gcd(a,n)= 1。

这时称求出的 x 为 a 的对模 n 乘法的逆元。

对于同余方程 ax= 1(mod n ), gcd(a,n)= 1 的求解就是求解方程

ax+ ny= 1,x, y 为整数。这个可用扩展欧几里德算法求出,原同余方程的唯一解就是用扩展欧几里德算法得出的 x 。

也就是gcd(a,n,x,y);
然后再(x = x%n + n)%n,得到最小的正整数x,即为a在模n意义下的逆元。

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz