A New Modular Multiplication Method in Public Key Cryptosystem
Modular multiplication is an important operation in several public key cryptosystems. This paper brings a novel idea based on the idea in the exponentiation computation. In this paper a new algorithm for modular multiplication for public key cryptosystem is presented. This proposed method is based on the following two ideas. The remainder in regard to n can be constructed from the remainder with modulus (2n+1) and the remainder with modulus (2n+2). It often happens that 2n+1 and 2n+2 can easily be factorized, even if n is a prime number or difficult to be factorized into prime factors. The performance of new algorithm using estimation of the computational complexity is observed, and it is shown that the procedure is much faster than the previous algorithms.