AN IMPROVED BINARY ALGORITHM FOR RSA

The normal form and modified normal form for binary redundant representations are defined. An improved binary algorithm to compute modular exponentiation for very large integers is proposed. It is shown that the proposed algorithm requires the minimum number of basic operations (modular multiplications) among all possible binary redundant representations. Compared to the binary algorithm, the proposed algorithm reduces the number of basic operations by 33%. Based on the proposed algorithm, a linear systolic array implementation of the RSA cryptographic system is presented, in which the total number of processing elements required is significantly reduced, and better complexity merit in terms of product of area and time of systolic implementation is achieved compared with a previous design based on binary algorithm.