模逆算法的分析、改进及测试

摘要：

公钥密码实现中,模逆算法经常是算法实现的瓶颈.通常求模逆的运算方法牵涉到大量的除法和减法操作,而除法操作需要大量的运算开销.基于现有的求最大公因子的方法,分析利用扩展欧几里德求模逆的方法,以及二进制扩展欧几里德算法,提出了利用二进制扩展欧几里德算法求模逆的方法,给出了几种算法性能比较的测试环境和测试结果.测试结果表明:改进的算法比利用扩展欧几里德求模逆的方法速度更快,对硬件实现更具有普遍性.

关键词：公钥密码体制、欧几里德算法、扩展欧几里德算法、模逆

所属期刊栏目：33

分类号：TP309.7(计算技术、计算机技术)

在线出版日期：2004-10-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：383-386,394