Low depth combinational finite field multiplier

摘要

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.