Back to results
US 2009/0157790 A1Published application
Method and apparatus for multiplying polynomials with a prime number of terms
AssigneeIntel Corporation
InventorsVinodh Gopal, Michael E. Kounavis
Life of this patent
Estimating the term…
Abstract
An efficient method and apparatus to compute a product of polynomials of degree n−1 where n is an arbitrary prime is provided. The total number of multiply operations and Arithmetic Logical Unit (ALU) operations to compute the product is minimized through the judicious use of polynomial evaluations at few points to decrease the number of multiplications while using only simple ALU operations.
Claims16
A method comprising:
- computing a product C of a polynomial A having n coefficients and a polynomial B having n coefficients, C having (2n−1) coefficients, where n is prime by:
- computing products of coefficients of A and coefficients of B for which indices (i, j) are equal;
- computing products of coefficients of A and B for which indices (i, j) are not equal and the sum of the indices is not equal to n or n−1;
- using the computed products to compute coefficients of C;
- and
- computing the nth and (n−1)th coefficients of C using a result of evaluating C at {1, −1} and the computed coefficients of C.
3 more elements
An apparatus comprising:
- a polynomial multiplier to compute a product C of a polynomial A having n coefficients and a polynomial B having n coefficients, C having (2n−1) coefficients, where n is prime, the polynomial multiplier to compute products of coefficients of A and coefficients of B for which indices (i, j) are equal, compute products of coefficients of A and B for which indices (i, j) are not equal and the sum of the indices is not equal to n or n−1, to use the computed products to compute coefficients of C and to compute the nth and (n−1)th coefficients of C using a result of evaluating C at {1, −1} and the computed coefficients of C.
An article including a machine-accessible medium having associated information, wherein the information, when accessed, results in a machine performing:
- computing a product C of a polynomial A having n coefficients and a polynomial B having n coefficients, C having (2n−1) coefficients, where n is prime by:
- computing products of coefficients of A and coefficients of B for which indices (i, j) are equal;
- computing products of coefficients of A and B for which indices (i, j) are not equal and the sum of the indices is not equal to n or n−1;
- using the computed products to compute coefficients of C;
- and
- computing the nth and (n−1)th coefficients of C using a result of evaluating C at {1, −1} and the computed coefficients of C.
3 more elements
A system comprising:
- a dynamic random access memory to store a polynomial A having n coefficients and a polynomial B having n coefficients;
- and
- a polynomial multiplier to compute a product C of A and B, C having (2n−1) coefficients, where n is prime, the polynomial multiplier to compute products of coefficients of A and coefficients of B for which indices (i, j) are equal, compute products of coefficients of A and B for which indices (i, j) are not equal and the sum of the indices is not equal to n or n−1, to use the computed products to compute coefficients of C and to compute the nth and (n−1)th coefficients of C using a result of evaluating C at {1, −1} and the computed coefficients of C.
Dependencies are inferred from the claim text.