TITLE:
Enhanced Euclid Algorithm for Modular Multiplicative Inverse and Its Application in Cryptographic Protocols
AUTHORS:
Boris S. Verkhovsky
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
JOURNAL NAME:
International Journal of Communications, Network and System Sciences,
Vol.3 No.12,
December
27,
2010
ABSTRACT: 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.