Space Complexity of Algorithm for Modular Multiplicative Inverse

• 作者: Boris S. Verkhovsky
• 来源期刊: 通讯、网络与系统学国际期刊(英文)
• 学科: 数学
• 关键词: MODULAR MULTIPLICATIVE INVERSE Public-Key Encryption SPACE Complexity Tight Upper Bound Extended EUCLID ALGORITHM Prefix Coding Enhanced EUCLID ALGORITHM Custom-Built Circuits
• 年，卷（期）: 2011,（6）
• 页码范围: 357-363
• 页数: 7页
• 分类号: O1

摘要

In certain computational systems the amount of space required to execute an algorithm is even more restrictive than the corresponding time necessary for solution of a problem. In this paper an algorithm for modular multiplicative inverse is introduced and its computational space complexity is analyzed. A tight upper bound for bit storage required for execution of the algorithm is provided. It is demonstrated that for range of numbers used in public-key encryption systems, the size of bit storage does not exceed a 2K-bit threshold in the worst-case. This feature of the Enhanced-Euclid algorithm allows designing special-purpose hardware for its implementation as a subroutine in communication-secure wireless devices.