若ab两数的乘积对正整数n取模的结果为1. 则称ab 互为另外一个的模逆.
如何标记?
若ab互为n的模逆  即b 为a
只有当 a 与 n 互素的时候 a 才是有模逆的. 其他情况下是不存在模逆的 比如 2 对26 就没有模逆.
这是个很简单的数学问题 大家动下手 画几笔就清楚了.我就不多罗嗦了.
大家能快速的求出11对123的模逆吗? (放心11和123是互素的.)
到了这里 如果使用笔算对b从2开始依次递加穷举的话将会非常辛苦 若将123换成一个更大一点的数 用笔算穷举更是不可能的.
写个程序帮我们穷举的确很棒 充分发挥了计算机的作用.
但这里 我介绍给大家另外一种巧妙的方法 ----
然后我们取第三列的最下面的一个数 再对123 取模 即得11 对123的模逆.
对于这个变换 不清楚的朋友我劝你们最好动笔画几下.
那样比我在这里说的起作用的多.嘿嘿~~
这个算法的好处:
我们编写这个算法的程序去求任何模逆都是非常高效的 它帮我们以及CPU都节省了不少时间.
后面的10是13211减掉的1211的倍数.意思为减掉10个1211.
我们可以用如下一段小程序来完成模逆的计算:
刚才费了这么大的劲 介绍了模逆 还是为了在给仿射密码的解密打地基.
根据简单的数论知识 我们知道其解密变换为: x =
也即 x =
a对26的模逆与(y-b)相乘后的积再对26取模 最终结果即为解密后的内容.
好了 仿射密码的理论介绍就到这里. 附件中为仿射密码学习的小软件. 附带源码. 希望大家用的上. 谢谢 !