Euclid 算法
今天在看RSA加密算法的时候看到了可以用扩充的euclid算法来简化d的计算。一查才发现原来euclid算法算法就是下面这个式子：
GCED (a, b) = GCED (b, a % b)
下面这个是著名求最大公约数的辗转相除算法的代码实现：
int Euclid_Algorithm (int m, int n)
{
int temp = m;
{
int temp = m;
if (!m || !n) return 0;
if (m < n) {m = n; n = temp;}
if (m < n) {m = n; n = temp;}
while (1) {
if (!(m = m % n)) return n;
if (!(n = n % m)) return m;
}
}
if (!(m = m % n)) return n;
if (!(n = n % m)) return m;
}
}
而扩展的euclid算法的原理是这样的：
k*k-1=1(mod 26)
k-1叫k的模逆, 可以用扩展的Euclid算法求出来。
ax = 1 (mod 26) 其中x = a-1
相当于 ax + by = 1，b = 26，求满足条件的一组x, y。当然我们只要x就好.
现在考虑一般的 ax + by = 1 如何求解。
因为满足条件的x, y存在的条件是GC&D(a, b) = 1.
然后有 ax + by = GC&D (a, b)
而同时有 bx' + (a % b)y' = GCED (b, a % b)
由Euclid定理GCED (a, b) = GCED (b, a % b)
所以, 有ax + by = bx' + (a % b)y'= bx' + (a - [a/b]*b)y'= bx' + ay' - [a/b]*b y'= ay' + b(x' - [a/b]y')
对应, 得x = y'，y = x' - [a/b]y'。[a/b]是a/b再取整。
特别的, 在b = 0的时候, GCED (a, b) = a = a * 1 + b * 0
即 x = 1, y = 0