Method and apparatus for multiplying polynomials with a prime number of terms

An apparatus comprising:

• an arithmetic and local unit (ALU) to perform ALU operations and a multiplier to perform other operations that implement a certain algorithm to perform polynomial multiplication, the certain algorithm including a first set of operations that comprises a subset of a second set of operations that implements a non-recursive Karatsuba algorithm (KA), the first set of operations also comprising at least one operation in addition to the second set of operations, wherein the certain algorithm comprises multiplying two respective polynomials that have respective prime numbers of respective terms, the certain algorithm employing only arithmetic and local unit (ALU) operations and other operations performed by a multiplier, the ALU operations comprising addition, subtraction, multiplication, and bit shifting operations, the certain algorithm resulting in a first number of multiply operations involved in multiplying certain polynomials that is less than a second number of multiply operations employed in KA multiplication of the certain polynomials, the certain algorithm including computing coefficients of a product C(x) of two n term polynomials A(x) and B(x) by first calculating a plurality of precomputed products for aibi wherein i=0 to n−1;
• and secondly calculating C(x)=(ai+aj)*(bi+bj)−aibi−ajbj for each i and j from 0 to n−1, further wherein calculation of C(x) involving aibi and ajbj corresponds to the precomputed products and are not recalculated for the calculation;
• the second calculating being based upon two-term Karatsuba multiplications using coefficients of the polynomials A(x) and B(x) for which respective indices i and j are not equal and also for which i+j is not equal to n or n−1, the ALU operations being performed by an ALU comprised in a public key encryption unit, the encryption unit also comprising a state machine and the multiplier, the state machine being to control sequence of the ALU operations performed by the ALU and the other operations performed by the multiplier to perform the first number of multiply operations, the encryption unit being comprised in an input/output (I/O) controller hub, the controller hub comprising a storage I/O controller to control communication with at least one storage device to be coupled to the controller hub, the communication being via a serial storage interconnect using a serial storage protocol.

A non-transitory machine-usable medium storing computer readable program code that when executed results in a machine performing the following operations:

• using a certain algorithm to perform polynomial multiplication, the certain algorithm including a first set of operations that comprises a subset of a second set of operations that implements a non-recursive Karatsuba algorithm (KA), the first set of operations also comprising at least one operation in addition to the second set of operations, wherein the certain algorithm comprises multiplying two respective polynomials that have respective prime numbers of respective terms, the certain algorithm employing only arithmetic and local unit (ALU) operations and other operations performed by a multiplier, the ALU operations comprising addition, subtraction, multiplication, and bit shifting operations, the certain algorithm resulting in a first number of multiply operations involved in multiplying certain polynomials that is less than a second number of multiply operations employed in KA multiplication of the certain polynomials, the certain algorithm including computing coefficients of a product C(x) of two n term polynomials A(x) and B(x) by first calculating a plurality of precomputed products for aibi wherein i=0 to n−1;
• and secondly calculating C(x)=(ai+aj)*(bi+bj)−aibi−ajbj for each i and j from 0 to n−1, further wherein calculation of C(x) involving aibi and ajbj corresponds to the precomputed products and are not recalculated for the calculation;
• the second calculating being based upon two-term Karatsuba multiplications using coefficients of the polynomials A(x) and B(x) for which respective indices i and j are not equal and also for which i+j is not equal to n or n−1, the ALU operations being performed by an ALU comprised in a public key encryption unit, the encryption unit also comprising a state machine and the multiplier, the state machine being to control sequence of the ALU operations performed by the ALU and the other operations performed by the multiplier to perform the first number of multiply operations, the encryption unit being comprised in an input/output (I/O) controller hub, the controller hub comprising a storage I/O controller to control communication with at least one storage device to be coupled to the controller hub, the communication being via a serial storage interconnect using a serial storage protocol.