FPGA Modular Multipliers using Hybrid Reduction Techniques

Modular multiplication is a key kernel in many computing fields. What makes this function so challenging are the very large word sizes – sometimes in the thousands of bits – that are typically required for the target applications. In this paper we propose a modular multiplication implementation based on a multi-stage hybrid reduction technique. Our proposed approach uses a parameterized number of multiplier-based reduction stages followed by a memory-based reduction. This construction allows for the multiplier-based stages to take advantage of Karatsuba multiplication, resulting in a reduced number of DSP Blocks. Our method also allows specifying the number of multiplier-based stages which adjusts the ratio of multipliers to memory blocks. The resource utilization of the proposed architecture outperforms the existing state-of-the-art modular multiplication designs while offering a user-defined way of distributing resources between memory and DSP Blocks.