加载中…求乘法逆元（模逆运算）
(2017-04-26 13:42:36)| 分类： 笔记 |
对于0~25这二十六个数字，如果整数a与26互质，那么存在结论
26个数字乘以a并对26取模（乘以a除以26取余数）可以对应的（0~25）中26个不同数字，前后形成唯一映射
这是乘法加密算法
如果知道取模后的值怎么对应到数乘取模之前的值，就是怎么解密
答案是求乘法逆元（模逆运算）
python程序：
#to find mod inverse of a and b
import gcd
def findmodinverse(a,b):
if gcd.gcd(a,b)!=1:
return None
u1,u2,u3=1,0,a
v1,v2,v3=0,1,b
while v3!=0:
q=u3//v3
v1,v2,v3,u1,u2,u3=(u1-q*v1),(u2-q*v2),(u3-q*v3),v1,v2,v3
return u1%b
其中gcd表示求最大公因数，就是if语句就是在判断是否互质，如果a和b不满足互质算法就没有意义
其中a表示相乘的因子，b表示取余的因子
算法并不好理解，但是可以求出模逆的值。
这个值乘以加密后的数再对b取模，可以得到加密前的数
print(i*7%26*findmodinverse(7,26)%26)
上面的语句叫i等于任意0到25之间整数，返回值一定是i本身
我猜想这一点也可以解释为什么有些程序语言以0为开头而不是以1开头
喜欢
0
赠金笔