Abstract: In public key cryptography application, getting multiplicative inverse of a modulo is often operating which usually adopts extended Euclid algorithm, but its use has limit. On the basis of actual application, a fast and suited embedded environment algorithm is proposed, which needs less memory and runs 5 times faster than extended Euclid algorithm.

Key words: Modulo inverse, Fast algorithm, Embedded environment, Public key cryptography

摘要： 在公钥密码应用中，求模逆元是一个常用的操作，通常使用扩展欧拉算法，但它的使用有一定的限制。该文根据实际应用的情况，提出了一个适合实际应用的求模逆元算法，其满足嵌入式环境下的内存需求，且速度也比扩展欧拉算法快5倍左右。

关键词: 模逆元, 快速算法, 嵌入式系统环境, 公钥密码学