Modular Square-and-Multiply Operation for Quadratic Residue Bases

[[abstract]]This paper introduces a new operation for modular exponentiation opera- tions. The number of modular operations will determine the computing performance of modular exponentiation under the assumption that the complexity of modular multipli- cation is the same as that of modular square. Unlike other schemes that are devoted to the reduction of the number of modular multiplication operations, the proposed operation performs modular square operation and modular multiplication operation together. To accelerate the proposed modular square-and-multiply operation, the lookup table scheme is introduced. The elements in this lookup table are computed according to the Chinese Remainder Theorem after the modulus is given. Every element is a partial result of modular square operations. The modular square operation can then work very efficiently. The modular square-and-multiply operation is derived from the modular square operation with a quadratic residue base. To sum up, modular exponentiation operations processed by the proposed operation can not only get speeded up in reducing the number of modular operations but also improve the performance of every modular operation