Lean multiplication of multi-precision numbers over GF(2m)

A computer-readable medium storing a sequence of instructions that when executed cause a computer to perform a cryptographic method of multiplying a first polynomial and a second polynomial over a finite field having 2m elements, wherein m is a positive integer, the method comprising:

• representing the first polynomial and the second polynomial as an array of n words having a size of at least two bits, wherein n is an integer;
• using a recursive algorithm to decompose a multiplication of the first polynomial and the second polynomial into a weighted sum of iteratively smaller subproducts;
• and
• using a nonrecursive algorithm to complete the multiplication when a size of the smaller subproducts is less than or equal to a predetermined size, the predetermined size being at least two words;
• and
• storing a cryptographic parameter associated with the multiplication in a memory.

A computer-implemented cryptographic method of multiplying a first polynomial and a second polynomial over a finite field having 2m elements, wherein m is a positive integer:

• representing the first polynomial and the second polynomial as n words having a size of at least two bits, wherein n is an integer greater than one;
• determining a partial result by calculating a weighted sum of one-word subproducts having weights of a form
• ∑
• n
• -
• 1
• j
• =
• 0
• ⁢
• z
• i
• +
• j
• for i=0, . . . , n−1, wherein i and j are index integers;
• updating the partial result by adding remaining one-word subproducts;
• and
• storing a cryptographic parameter associated with the multiplication in a memory.

A computer-readable medium storing a sequence of instructions that when executed cause a computer to perform a cryptographic method of multiplying a first polynomial and a second polynomial over a finite field having 2m elements, wherein m is a positive integer, the method comprising:

• representing the first polynomial and the second polynomial as n words having a size of at least two bits, wherein n is an integer greater than one;
• determining a partial result by calculating a weighted sum of one-word subproducts having weights of a form
• ∑
• n
• -
• 1
• j
• =
• 0
• ⁢
• z
• i
• +
• j
• for i=0, . . . , n−1, wherein i and j are index integers;
• updating the partial result by adding remaining one-word subproducts;
• and
• storing a cryptographic parameter associated with the multiplication in a memory.

A computer-implemented cryptographic method of multiplying a first polynomial and a second polynomial over a finite field having 2m elements, wherein m is a positive integer:

• representing a product of the first polynomial and the second polynomial as a weighted sum of one-word subproducts;
• identifying pairs of redundant one-word subproducts;
• removing the pairs of redundant one-word subproducts from the weighted sum, thereby obtaining a revised weighted sum;
• and
• storing a cryptographic parameter associated with the multiplication in a memory.

A computer-readable medium storing a sequence of instructions that when executed cause a computer to perform a cryptographic method of multiplying a first polynomial and a second polynomial over a finite field having 2m elements, wherein m is a positive integer, the method comprising:

• representing a product of the first polynomial and the second polynomial as a weighted sum of one-word subproducts;
• identifying pairs of redundant one-word subproducts;
• removing the pairs of redundant one-word subproducts from the weighted sum, thereby obtaining a revised weighted sum;
• and
• storing a cryptographic parameter associated with the multiplication in a memory.

A computer-implemented cryptographic method, comprising:

• receiving a first operand and a second operand, the first operand and the second operand representing a first polynomial over a finite field having 2m elements, wherein m is a positive integer, and a second polynomial over the finite field having 2m elements;
• multiplying the first operand and the second operand in a multiplication process, the multiplication process comprising:
• using a recursive algorithm to reduce the multiplication of the first operand and the second operand into a weighted sum of smaller subproducts;
• and
• using a nonrecursive algorithm to multiply the smaller subproducts when a size of the smaller subproducts is less than or equal to a predetermined size, the predetermined size being at least two words;
• storing a cryptographic parameter associated with the multiplication in a memory;
• and outputting the cryptographic parameter associated with the multiplication.

A cryptographic apparatus comprising:

• means for receiving a first polynomial and a second polynomial over a finite field having 2melements, wherein m is a positive integer;
• means for storing the first polynomial and the second polynomial as a series of words;
• a processor for executing computer-readable instructions for recursively multiplying the first polynomial and the second polynomial by dividing the stored first and second polynomials into multiple smaller subproducts until an input size of the subproducts is less than a predetermined size and for executing-computer-readable instructions for nonrecursively multiplying the subproducts when the size of the inputs is less than the predetermined size, the predetermined size being at least two words;
• and
• means for outputting the product of the first polynomial and the second polynomial.