As we know one of the most important computer arithmetic operations in public-key cryptosystems for information security is modular exponentiation, and the Montgomery modular reduction algorithm is very useful for modular exponentiation due to its simplicity and high speed. As the modular squaring operation in finite field can be done by a simple shift operation when a normal basis is used, and the modular multiplications and modular squaring operations in our proposed signed-digit recoding scheme can be executed in parallel, by using our proposed generalized r-radix signed-digit folding algorithm, hardware design and parallel technique, we can effectively decrease the computational complexity.