A way to speed up the Montgomery Multiplication by distributing the multiplier operand bits into${\mbi {k}}$partitions is proposed. All of them process in parallel and use an identical algorithm. Each partition executes its task in${\mbi {n/k}}$steps. Even though the computationstep operates in radix${\mbi {2^k}}$, the complexity is reduced by the use of a limited digit set. Experiments with a 90-nm cell library show that the hardware cost and its complexity have a linear growth according to the number of partitions. Besides the gain in speed, the proposal reduces power consumption for multiplication operands with 256, 512, 1024, and 2048 bits. The uniform treatment of partition hardware design enables the realization of a fault-tolerant hardware.

This paper proposes a new approach to speed up the Montgomery Multiplication by distributing the multiplier operand bits into k partitions that can process in parallel. Each partition executes in n/k steps. A computation step, although operating in radix 2k, has its complexity reduced by the use of a limited digit set. Experiments with a 90nm cell library show that the hardware cost and its complexity have a linear growth with the number of partitions. Besides the gain in speed, the approach provides 20% average reduction in energy consumption for multiplication operands with 256, 512, 1024, and 2048 bits.