Academic Journals Database
Disseminating quality controlled scientific knowledge

Space Complexity of Algorithm for Modular Multiplicative Inverse

Author(s): Boris S. Verkhovsky

Journal: International Journal of Communications, Network and System Sciences
ISSN 1913-3715

Volume: 04;
Issue: 06;
Start page: 357;
Date: 2011;
Original page

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

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.

Tango Rapperswil
Tango Rapperswil

     Save time & money - Smart Internet Solutions