Academic Journals Database
Disseminating quality controlled scientific knowledge

Enhanced Euclid Algorithm for Modular Multiplicative Inverse and Its Application in Cryptographic Protocols

Author(s): Boris S. Verkhovsky

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

Volume: 03;
Issue: 12;
Start page: 901;
Date: 2010;
Original page

Keywords: Extended-Euclid Algorithm | Modular Multiplicative Inverse | Public-Key Cryptography | RSA Cryptocol | Rabin Information Hiding Algorithm | ElGamal Encryption/Decryption | NTRU Cryptosystem | Computer Simulation | Low Memory Devices

Numerous cryptographic algorithms (ElGamal, Rabin, RSA, NTRU etc) require multiple computations of modulo multiplicative inverses. This paper describes and validates a new algorithm, called the Enhanced Euclid Algorithm, for modular multiplicative inverse (MMI). Analysis of the proposed algorithm shows that it is more efficient than the Extended Euclid algorithm (XEA). In addition, if a MMI does not exist, then it is not necessary to use the Backtracking procedure in the proposed algorithm; this case requires fewer operations on every step (divisions, multiplications, additions, assignments and push operations on stack), than the XEA. Overall, XEA uses more multiplications, additions, assignments and twice as many variables than the proposed algorithm.
Affiliate Program     

Tango Jona
Tangokurs Rapperswil-Jona