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

摘要

This paper discusses the algorithm on Z( p ) for computing inverse elements, while p is a prime. The paper introducesrnthe concept of order of reversible element and the algorithm called the iterative elimination by bit. The complexity of this algorithmrnis O((logpn)2).%讨论在模n=pk(p是素数)剩余类环R中计算逆元的算法.本文引入可逆元的阶的概念,在对阶的性质进行讨论的基础上,提出计算逆元的逐位消除算法.算法的时间复杂度为O(k2)=O((logpn)2).