最近写了C语言的大作业,其中有一些个人的改进,让我觉得可以写一篇博客来记录一下。
简介
大作业的要求是编程实现仿射密码的加密和解密,仿射密码是什么自行百度,这篇博客主要内容就两个
- 求a模n的乘法拟元
- 加解密函数的一种通用化改进
乘法逆元
a模b的乘法逆元表示如下 $(ax)%b=1$,x就是a的乘法逆元,上面式子可以变成一个方程,$ax=by+1$,求逆元就是解出x和y。
扩展欧几里得算法
已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y(其中一个很可能是负数),使它们满足贝祖等式 $ax+by=gcd(a,b)$
如果a和b互质,上式就可以转化为$ax=-by+1$,几乎就是乘法逆元的形式了,所以可以用扩展欧几里得算法来求出x和y。
递归实现
网上几乎所有的扩展欧几里得算法都是递归实现的,而且递归的实现很不好描述,这里直接放一篇网上的文章算法学习笔记(8):拓展欧几里得
迭代实现
如果只是贴别人的文章那就太敷衍了,而且我就不会写这篇文章了,所以重点是这个。
这还得从我翻百度百科:扩展欧几里得算法的时候说起,我看见了这个
然后思路一下就打开了,这不比用递归的方法好直观多了,只要开一个2x3的数组,然后辗转相减直到a或b变成gcd(a,b),它所在的那一列下面的两个分量就是所求的x和y,代码如下:
1 | int inv(int a,int b){ |
返回-1是没有a和b不互质的情况,如果确保传入的a和b合法可以修改for的条件直接在外面返回。注意,求出来的逆元有可能是个负数,所以需要加上b之后再取余,确保是正数。
加解密函数改进
这是一个数学问题,这是我在尝试压行的时候发现的。
首先我们来看看原版的加解密函数是什么样
$$
c_i=(\alpha p_i+\beta)%n
p_i=\alpha^{-1}(c_i-\beta)%n
$$
不难发现,上面其实都是一次函数,所以可以把它们化成标准形式,加密函数已经是标准形式了,所以主要就是解密函数。这里有一点需要注意,如果$\beta$比$c_i$大,那会出现负数。
$$
p_i=\alpha^{-1}(c_i-\beta)%n
=\alpha^{-1}(c_i+(26-\beta))%n
=(\alpha^{-1}c_i+\alpha^{-1}(26-\beta))%n
$$
所以我们只需要写一个求解一次函数的函数,然后加密或者解密其实就是传入的参数不同,代码如下:
1 | int f(int a,int b,int x){ |
代码仅作为参考,我分这么多个函数只是为了看起来清晰一点,每个函数只做一件事,实际上完全可以把f和trans合起来,然加密和解密函数直接写成宏的形式,总之写法有很多,取决于每个人的风格吧。
结尾
写完这两个算法,大作业就差不多了,剩下的就是些交互程序的写法,这些都好写,之后我可能会写篇迭代版求乘法逆元的优化。