Modular Multipliers using Hybrid Reduction Techniques

A method comprising:

• receiving a multiplicand value, a multiplier value, and a modulus value;
• multiplying the multiplicand value and the multiplier value to obtain an initial product;
• performing a first coarse-grain partial modular reduction on the initial product based on the modulus value using a first type of modular reduction to obtain a first reduced interim product;
• performing a second coarse-grain partial modular reduction on the first reduced interim product based on the modulus value using a second type of modular reduction to obtain a second reduced interim product;
• and
• performing a fine-grain partial modular reduction on the second reduced interim product to obtain a final modular reduction value.

Modular reduction circuitry comprising:

• multiplication circuitry to multiply an input multiplicand value of n bits with an input multiplier value of n bits to obtain a product;
• first partial modular reduction circuitry to perform a first partial modular reduction on the product based on an n-bit modulus value using multiple stages of multiplier-based modular reduction to obtain a first reduced interim product;
• second partial modular reduction circuitry to perform a second partial modular reduction on the first reduced interim product based on the modulus value using lookup-table-based modular reduction to obtain a second reduced interim product;
• and
• third partial modular reduction circuitry to perform a final modular reduction on the second reduced interim product based on the modulus value to obtain an n-bit final modular reduction value.