Modular Multipliers using Hybrid Reduction Techniques
Integrated circuit devices, methods, and circuitry for implementing and using a hybrid modular multiplier circuit using a number of different modular reduction techniques are provided. Integrated circuitry may include multiplication circuitry to multiply an input multiplicand value with an input multiplier value to obtain a product, first coarse-grain modular reduction circuitry to partially reduce the product based on a modulus value using a first type of modular reduction, second coarse-grain modular reduction circuitry to further reduce the product based on the modulus value using a second type of modular reduction, and fine-grain modular reduction circuitry to finally reduce the product based on the modulus value using a third type of modular reduction to produce a final modular reduction result.
1 . Integrated circuitry comprising:
multiplication circuitry to multiply an input multiplicand value with an input multiplier value to obtain a product;
first coarse-grain modular reduction circuitry to partially reduce the product based on a modulus value using a first type of modular reduction;
second coarse-grain modular reduction circuitry to further reduce the product based on the modulus value using a second type of modular reduction; and
fine-grain modular reduction circuitry to finally reduce the product based on the modulus value using a third type of modular reduction to produce a final modular reduction result.
2 . The integrated circuitry of claim 1 , wherein the first coarse-grain modular reduction circuitry comprises multiplier-based modular reduction circuitry.
3 . The integrated circuitry of claim 2 , wherein the multiplier-based modular reduction circuitry comprises a plurality of multiplier-based modular reduction stages.
4 . The integrated circuitry of claim 3 , wherein the plurality of multiplier-based modular reduction stages comprises a first stage that reduces the product by a first number of bits and a second stage that further reduces the product by a second number of bits, wherein the first number of bits is greater than the second number of bits. comprise a rectangular multiplier formed using a plurality of square multipliers.
5 . The integrated circuitry of claim 3 , wherein the plurality of multiplier-based modular reduction stages comprises:
a first stage having a first multiplier that multiplies a first constant value having a width n with a first portion of most significant bits of the product greater than the lowest n bits of the product to generate a first reduced product; and
a second stage having a second multiplier that multiplies a second constant value having the width n with a second portion of most significant bits of a portion of the first reduced product greater than the lowest n bits of the first reduced product.
6 . The integrated circuitry of claim 5 , wherein the first multiplier and the second multiplier are rectangular multipliers, wherein the first multiplier has dimensions of 2n×n and wherein the second multiplier has dimensions of 2n×a bitwidth less than n.
7 . The integrated circuitry of claim 6 , wherein the first multiplier and the second multiplier are rectangular multipliers, wherein the bitwidth less than n is equal to n/2+1.
8 . The integrated circuitry of claim 2 , wherein the multiplier-based modular reduction circuitry comprises multipliers formed primarily of embedded digital signal processing blocks in programmable logic circuitry.
9 . The integrated circuitry of claim 1 , wherein the second coarse-grain modular reduction circuitry comprises lookup-table-based modular reduction circuitry, wherein the input multiplicand value and the input multiplier value have a common bitwidth of n, and wherein the lookup-table-based modular reduction circuitry comprises a plurality of lookup tables indexed by chunks of a portion of bits of the product greater than n resulting after reduction in the first coarse-grain modular reduction circuitry.
10 . The integrated circuitry of claim 9 , wherein the plurality of lookup tables are formed primarily of embedded memory blocks in programmable logic circuitry.
11 . The integrated circuitry of claim 1 , wherein the fine-grain modular reduction circuitry comprises selection circuitry to select the final modular reduction between two possible values of the final modular reduction based on a sign of one of the two possible values.
12 . 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.
13 . The method of claim 12 , wherein the first type of modular reduction comprises multiplier-based modular reduction.
14 . The method of claim 12 , wherein the first coarse-grain partial modular reduction, when implemented on a programmable logic device, consumes more digital signal processing resources and fewer memory resources than the second coarse-grain partial modular reduction.
15 . The method of claim 12 , wherein the second type of modular reduction comprises lookup-table-based modular reduction.
16 . The method of claim 12 , wherein performing the fine-grain partial modular reduction comprises:
indexing a plurality of most significant bits of the second reduced interim product to a table to obtain a first value equal to an integer value K 1 multiplied by the modulus M and a second value equal to an integer value K 2 multiplied by the modulus M, wherein K 2 =K 1 +1;
subtracting the first value from the second reduced interim product to obtain a first final modular reduction value candidate;
subtracting the second value from the second reduced interim product to obtain a second final modular reduction value candidate; and
selecting the final modular reduction value from between the first final modular reduction value candidate and the second final modular reduction value candidate.
17 . The method of claim 16 , wherein the final modular reduction value is selected based on a sign of the second final modular reduction value candidate.
18 . 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.
19 . The circuitry of claim 18 , wherein the second partial modular reduction circuitry comprises:
a plurality of lookup tables indexed by respective chunks of bits of a portion of the most significant bits of the first reduced interim product greater than n, wherein the plurality of lookup tables output respective constant values of n bits wide based on the respective chunks; and
addition circuitry to add the respective constant values to the lowest n bits of the first reduced interim product in parallel.
20 . The circuitry of claim 18 , wherein the third partial modular reduction circuitry comprises:
memory circuitry comprising a table holding a plurality of pairs of a first value equal to an integer value K 1 multiplied by the modulus M and a second value equal to an integer value K 2 multiplied by the modulus M, wherein K 2 =K 1 +1, for different values of K 1 and K 2 , wherein the table is indexed to a selection of most significant bits of the second reduced interim product, including bits of the second reduced interim product greater than n and a most significant bit of the lower n bits of the second reduced interim product, to provide a selected pair of the first value and the second value;
first subtraction circuitry to subtract the first value from the second reduced interim product to obtain a first final modular reduction value candidate;
second subtraction circuitry to subtract the second first value from the second reduced interim product to obtain a second final modular reduction value candidate; and
selection circuitry to select the final modular reduction value from between the first final modular reduction value candidate and the second final modular reduction value candidate.