欧几里得算法

来源:百度知道 编辑:UC知道 时间:2024/06/16 02:41:19
在RSA密码体系中,欧几里得算法是加密或解密运算的重要组成部分。它的基本运算过程就是解 x*a=1(mod n) 这种方程。

The Problem
整个解的过程是这样的,我们用一个例子来说明。
当a=1001 ,n=3837时
方程为 x * 1001 = 1 (mod 3837)

求解过程:

3837 = 3 * 1001 + 834
1001 = 1 * 834 + 167
834 = 4 * 167 + 166
167 = 166 + 1

所以

1 = 167 - 166
= 167 - (834 - 4 * 167)
= 5 * 167 - 834
= 5 *(1001 - 834) - 834
= 5 * 1001 - 6 *834
= 5 * 1001 - 6 * (3837 -3 *1001)
= 23 * 1001 - 6 *3837

然后对等式两端同时除以模3837得

23 * 1001 = 1 (mod 3837)
于是 x = 23

那如果输入3837 1001,怎么算呢?

计算过程一模一样,只是最后对1001取模:
1 = 167 - 166
= 167 - (834 - 4 * 167)
= 5 * 167 - 834
= 5 *(1001 - 834) - 834
= 5 * 1001 - 6 *834
= 5 * 1001 - 6 * (3837 -3 *1001)
= 23 * 1001 - 6 *3837
然后对等式两端同时除以模1001得

6 * 3837 = 1 (mod 1001)
于是 x = 6

那个不是等号,是同余符号.要解同余式axmod(m)同余于1.a和m要互素,根据欧几里得算法反过来找出唯一满足as+mt=1的整数s.再将s乘以同余式左边,答案就出来了