在RSA密码体系中,欧几里得算法是加密或解密运算的重要组成部分.它的基本运算过程就是解x*a=1(modn)这种方程.TheProblem整个解的过程是这样的,我们用一个例子来说明.当a＝1001,n＝3837时方程

Question

在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,怎么算呢?

Answer 1

计算过程一模一样,只是最后对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