Low depth combinational finite field multiplier
View Patent ↗A method for generating a design of a multiplier is disclosed. The method generally includes steps (A) to (C). Step (A) may generate a first circuit comprising a plurality of polynomial results of a particular multiplier scheme based on a plurality of parameters of the multiplier. The first circuit is generally configured to multiply a plurality of polynomials. Step (B) may generate a second circuit comprising a plurality of polynomial evaluators based on the parameters. The second circuit may be (i) connected to the first circuit and (ii) configured to evaluate a polynomial modulo operation. Step (C) may generate the design of the multiplier in combinational logic by optimizing a depth of a plurality of logic gates through the first circuit and the second circuit. A product of the polynomials generally resides in a finite field.
1. A computer-implemented method for generating a hardware multiplier circuit, the computer comprising a processor and a memory device, the method comprising:
selecting, by the processor, a Karatsuba multiplier scheme from among a plurality of multiplier schemes in response to an iteration parameter being greater than zero, wherein said plurality of multiplier schemes includes the Karatsuba multiplier scheme and a non-Karatsuba multiplier scheme;
generating, by the processor, a first circuit configured to (i) multiply a plurality of coefficients of two polynomials to generate a plurality of partial products based on a plurality of parameters of said Karatsuba multiplier scheme, and (ii) combine said partial products to generate an intermediate product, wherein each polynomial comprises n components, and wherein a number of said partial products generated is less than 2n;
generating, by the processor, a second circuit configured to perform a polynomial modulo operation on said intermediate product to generate a final product of said polynomials based on said parameters and a modulo polynomial, wherein said final product of said polynomials resides in a finite field, and wherein said second circuit is connected to said first circuit; and
reducing, by the processor, a depth of a plurality of logic gates through said first circuit and said second circuit to generate a reduced depth combinational logic circuit, wherein said hardware multiplier circuit comprises said reduced depth combinational logic circuit.
2. The method according to claim 1 , wherein said Karatsuba multiplier scheme comprises a multiplier of size N/2K, where N is a dimension of said polynomials and K is a number of iterations of a multiplier circuit in said particular multiplier scheme.
3. The method according to claim 2 , wherein at least one of said iterations of said multiplier circuit is implemented using a plurality of logical AND gates and a plurality of logical XOR gates.
4. The method according to claim 1 , wherein said reducing comprises the step of:
generating a plurality of modified evaluators by substituting one of more formulas that calculate bits of said intermediate product into a plurality of polynomial evaluators in said second circuit.
5. The method according to claim 4 , wherein said reducing further comprises the step of:
eliminating one or more redundant summands in said modified evaluators in said second circuit.
6. The method according to claim 5 , wherein said reducing further comprises the step of:
reorganizing a sequence of operations in said modified evaluators in said second circuit such that said modified evaluators form balanced binary tree formulas.
7. The method according to claim 1 , wherein said partial products are implemented as a plurality of logical AND gates and said intermediate product is implemented as a plurality of logical XOR gates.
8. The method according to claim 1 , wherein each polynomial received by said first circuit comprises a dimension of N, wherein said intermediate product comprises a dimension of 2N−1, and wherein said final product of said polynomials generated by said second circuit comprises a dimension of N.
9. An apparatus, comprising:
a memory device configured to store program instructions; and
at least one processor device coupled to the memory device, wherein the at least one processor device is configured to execute the stored program instructions to implement a process for building a hardware multiplier circuit, the process comprising:
selecting, by the processor, a Karatsuba multiplier scheme from among a plurality of multiplier schemes in response to an iteration parameter being greater than zero, wherein said plurality of multiplier schemes includes the Karatsuba multiplier scheme and a non-Karatsuba multiplier scheme;
generating a first circuit configured to (i) multiply a plurality of coefficients of two polynomials to generate a plurality of partial products based on a plurality of parameters of said Karatsuba multiplier scheme, and (ii) combine said partial products to generate an intermediate product, wherein each polynomial comprises n components, and wherein a number of said partial products generated is less than 2n;
generating a second circuit configured to perform a polynomial modulo operation on said intermediate product to generate a final product of said polynomials based on said parameters and a modulo polynomial, wherein said final product of said polynomials resides in a finite field, and wherein said second circuit is connected to said first circuit; and
reducing a depth of a plurality of logic gates through said first circuit and said second circuit to generate a reduced depth combinational logic circuit, wherein said hardware multiplier circuit comprises said reduced depth combinational logic circuit.
10. The apparatus of claim 9 , wherein each polynomial received by said first circuit comprises a dimension of N, wherein said intermediate product comprises a dimension of 2N−1, and wherein said final product of said polynomials generated by said second circuit comprises a dimension of N.