Patent ID: 7392276

Claim:
A method of operating a multiplication circuit in a cryptographic application to compute, with fewer memory accesses, the product of two operands (X and Y) at least one of which is substantially wider than the multiplication circuit, the multiplication circuit having a pair of word-wide operand inputs and a two-word-wide product output, where a word is a specified number of bits, each of the operands composed of a plurality of contiguous ordered word-wide operand segments (x k and y m ) characterized by specific weights (k and m), the multiplication circuit having access to a memory, the method comprising the steps of: loading word-wide operand segments of the two operands in a specified order from the memory into the multiplication circuit, the multiplication circuit including at least two registers (RX and RY) having access to said memory for temporarily holding the loaded segments; multiplying the loaded segments to obtain two-word-wide intermediate products, the intermediate products having a weight equal to the sum of weights of the loaded segments; adding intermediate products of the same weight in an accumulator, the accumulator having a size of three words plus a number of carry bits sufficient for handling a specified maximum operand size, the accumulator connected to a two-word input register (RZ) for temporarily holding any previously added products of a specified weight and a two-word output register (RR) for holding results of an addition step, said registers (RZ and RR) having access to said memory; and storing accumulated results from said output register (RR) back into said memory at least after accumulating all intermediate products of the specified weight; wherein the specified order for loading operand segments into said registers is a sequence defined by the resulting intermediate product weights, wherein the multiplying step is done in successive groups of two adjacent product weights, with the sequence within a group being selected such that, other than a first multiply operation in a given group, at most one of the operand segments need be read from memory into one register (RX or RY), the other operand segment already being stored in the other register (RY or RX) from the immediately preceding multiply operation.