Analytical Modular Arithmetics and Complexity Analyses

Chia-Long Wu 1 , Der-Chyuan Lou 2 , and Te-Jen Chang 2

1 Department of Aviation & Communication Electronics, Chinese Air Force Institute of Technology

2 Department of National Defense , Chung Cheng Institute of Technology, National Defense University

Abstract

Most modern cryptographic protocols, which require a large number of processing steps, are based on modular arithmetic. We know modular arithmetic is the most dominant part of the computation which is performed in the RSA encryption system. The operation is time-consuming for large operands. Many relevant computer security papers are issued in many journals and reports to describe how to reduce the computational complexities in the cryptosystems. In this paper, we describe the modular arithmetic and some improved algorithms. These algorithms in the modular arithmetic are binary method, common multiplicand multiplication method, and signed-digit recoding method, addition chain method, and Montgomery algorithm and so on. Some improved algorithms will be depicted respectively such as dot counting method, complement recoding method, residue number system method, and sliding window method. We will compare the computational complexities for the performance of the described methods.

 Keywords: Binary method , signed-digit recoding , algorithm, sliding window technique, RSA cryptosystem.