一个求最大公因数和倒数的新算法及应用

A Computer Algorithm for the Computation gcd or Inverse

提出了一个求最大公因数和倒数的迭代算法,该算法可求得任意两个正整数a,m的最大公因数,如果(a,m)=1,可求得a关于模m的倒数。具体计算时对模数m是奇数偶数分别考虑。主要特点是避免了长整数除法和幂运算。以RSA中密钥的计算说明算法的应用。

This paper prsents a computer algorithm for the computation ( a , m ) or inverse of a modulo m without long integer devision,the algorithm include algorithm A for modulo odd, and algorithm B for modulo 2n, algorithm C for modulo event. An example about RSA key computation is given.