A parallel k-partition method to perform Montgomery Multiplication

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 2^k, 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.