TITLE:
Space Complexity of Algorithm for Modular Multiplicative Inverse
AUTHORS:
Boris S. Verkhovsky
KEYWORDS:
Modular Multiplicative Inverse, Public-Key Encryption, Space Complexity, Tight Upper Bound, Extended Euclid Algorithm, Prefix Coding, Enhanced Euclid Algorithm, Custom-Built Circuits
JOURNAL NAME:
International Journal of Communications, Network and System Sciences,
Vol.4 No.6,
June
17,
2011
ABSTRACT: 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.