在Z(pk)中计算逆元的逐位消除算法

• 作者: 刘萍
• 来源期刊: 计算机与现代化
• 学科: 工学
• 关键词: 剩余类环 逆元 逐位消除法
• 年，卷（期）: 2012,（7）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 41-43
• 分类号: TP301.6
• 字数: 1618字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-2475.2012.07.011

摘要

讨论在模n=pk(p是素数)剩余类环R中计算逆元的算法.本文引入可逆元的阶的概念,在对阶的性质进行讨论的基础上,提出计算逆元的逐位消除算法.算法的时间复杂度为O(k2)=O((logpn)2).