UC知道欧几里得算法
来源：百度知道 编辑：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，怎么算呢？
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乘以同余式左边,答案就出来了