辗转相除法是用来计算两个整数的最大公约数。假设两个整数为a和b，他们的公约数可以表示为gcd(a,b)。如果gcd(a,b) = c,则必然a = mc和b = nc。a除以b得商和余数，余数r可以表示为r = a - bk，k这里是系数。因为c为 a和b的最大公约数，所以c也一定是r的最大公约数，因为r = mc - nck = (m-nk)c。
因此gcd(a,b) = gcd(b,r)，相当于把较大的一个整数用一个较小的余数替换了，这样不断地迭代，直到余数为0，则找到最大公约数。
举例两个整数为1071和462：
第一步：1071 / 462 = 2 * 462 + 147
第二步：462 / 147 = 3 * 147 + 21
第三步：147 / 21 = 7 * 21 + 0
此时余数为零，则21为两个数的最大公约数。
贝祖公式表明对于任意两个整数a和b，都可以找到一对可为负的整数x和y，可以使等式xa + yb = m，其中m为a和b的最大公约数，合理性稍加思考可得。如果m为1说明a和b互素。所以在互素的情况下，xa + yb = 1。这个等式对于求乘法逆元有很大的帮助。
那么如何通过贝祖公式及扩展欧几里得算法来求乘法逆元呢？举一个例子来描述什么是乘法逆元。如果ab mod m = 1，或者可以表示为ab ≡ 1 mod m，这里b就是a关于模数m的乘法逆元。计算乘法逆元的方法就是扩展欧几里得算法，以下通过一个例子来帮助理解：
假设我们要求3 关于模26的乘法逆元(隐含了3和26的最大公约数为1，即互素)。当a = 3，b = 26，则根据贝祖公式，存在整数x和y，3x + 26y = 1。
思路就是等号两边同时mod 26，等式则变成(3x + 26y) mod 26 = 1 mod 26，根据模运算的性质(a + b) mod m = (a mod m + b mod m) mod m。
所以展开等式(3x mod 26 + 26y mod 26) mod 26 = 1 mod 26。化简最终得到(3x mod 26) mod 26 = 1 mod 26。我们发现3x mod 26 = 1正好符合了乘法逆元的定义，所以欧几里得算法就是解x的关键。
下面将通过辗转相除法来求x：
第一步：26 = 3 * 8 + 2
第二步：3 = 2 * 1 + 1
统一将余数换到等号左边：
2 = 26 - 3 * 8
1 = 3 - 2 * 1
将第一行的2替换到第二行，保证等式左边永远为1，等式右边变成仅由3x + 26y组成。
1 = 3 - (26 - 3 * 8) * 1 = 3 * 9 + (-1) * 26
可得x = 9
最后9就是3关于模26的乘法逆元。它可以应用于仿射加密。
附：仿射加密的公式e(x) = ax + b mod m， 其中a与m互素， b为移动距离。
仿射解密公式d(x) = a-1(x - b) mod m
网友评论