The k-ary Montgomery modular inverse over nonbinary computers

摘要

This paper presents a k-ary Montgomery modular inverse algorithm over nonbinary computers by using Sedjelmaci's right shift k-ary greatest common divisor scheme. Over traditional binary computers, Kaliski's scheme can output Montgomery modular inverse Q~(-1)2_n mod P, where P is coprime to Q and n is the bit length of P. Over k-ary computers, our algorithm can discover the k-ary Montgomery inverse Q~(- 1)k_m mod P, where P, Q, and k are pairwise relatively prime positive integers and m = log kP. In the worst case, the computational cost of our algorithm is O(m~2)k-ary digit operations.