Author(s)

Boris S. Verkhovsky

.

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.

Modular Multiplicative Inverse, Public-Key Encryption, Space Complexity, Tight Upper Bound, Extended Euclid Algorithm, Prefix Coding, Enhanced Euclid Algorithm, Custom-Built Circuits

B. Verkhovsky, "Space Complexity of Algorithm for Modular Multiplicative Inverse," International Journal of Communications, Network and System Sciences, Vol. 4 No. 6, 2011, pp. 357-363. doi: 10.4236/ijcns.2011.46041.