欧几里德算法及扩展算法

发表于 | 更新于: | 分类于 | 阅读次数:
字数统计: 470 | 阅读时长 ≈ 2

欧几里得算法

又称碾转相除法，用于计算两整数a, b 的最大公约数。

1
2
3
4
5
6
7
8
9
10
11
12
int max(int a, int b)
{
	int c;
	c = a % b;
	while (c != 0)
	{
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}

原理依赖于下面定理：

两个整数的最大公约数等于其中较小的那个数和两数相除的最大公约数。

证明：
设 a = kb +r， 则r = a mod b
假设d为a, b的一个公约数
r = kb - a
r/d = kb/d - a/d
可知r/d为整数，因此d也是a, b, a%b的公约数， 则得证。

欧几里得扩展算法

因为在学习RSA的共模攻击，所以复习一下欧几里得算法，但是关键是欧几里得算法扩展：

如果gcd(a, b) = c，则存在x, y，使得c = ax + by。

证明：

　　设 a>b
　　当 b = 0时，gcd(a, b) = a，此时x = 1, y = 0。
　　假设 a*x1 + b*y1 = gcd(a, b)
　　则 b*x2 + (a mod b)*y2 = gcd(b, a mod b)
　　根据 gcd(a, b) = gcd(b, a mod b)　　
　　可得 a*x1 + b*y1 = b*x2 + (a mod b)*y2　　
　　因为 a mod b = a - (a/b)*b //这里 ‘/‘ 是整除　　
　　所以 a*x1 + b*y1 = b*x2 + (a - (a/b)*b)*y2
　　　　　　　　　　　= b*x2 + a*y2 - (a/b)*b*y2
　　　　　　 gcd(a, b) = a*y2 + b*(x2 - (a/b)*y2)
　　对比 a*x1 + b*y1 = gcd(a, b)　　
　　发现 x1 = y2
　　　 　 y1 = x2 - (a/b)*y2　　

算法代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
int e_gcd(int a, int b, int x, int y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    int ans = e_gcd(b, a%b, x, y);
    int t = x;
    x = y;
    y = x - (a/b)*y;
    return ans;
}

乘法逆元

什么叫乘法逆元？

形如a*x mod b ≡ 1
我们称x是a关于f的乘法逆元，还有另一种表达式：

1
a*x + b*y = 1

也就是gcd(a, b) = 1

在RSA共模攻击中，求乘法逆元函数如下

1
2
3
4
5
6
def egcd(a, b):
    if a == 0:
          return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
look at here !!
0%