A fast modular square computing method based on the generalized Chinese remainder theorem for prime moduli

摘要

This paper introduces a very efficient way to compute modular exponentiations modulo to prime numbers. A prime modular exponentiation operation is replaced by two modular operations employed with decomposable moduli. Each substitute modular operation can be performed with the generalized Chinese remainder theorem (GCRT) for computing efficiency. Due to the independent computing property of the GCRT, these two substitute operations can be computed concurrently. Assuming the parallel computation, the computation complexity is better than the conventional modular exponentiation operations. The computational costs is reduced approximately to 22% if these factors of decomposable moduli are on average in quarter bit lengths of decomposable moduli and the smallest factor is in half average bit lengths. (C) 2003 Elsevier Inc. All rights reserved.