Patent ID: 7296049

Claim:
An interstitial product generator, comprising: a first shift register configured to output a multiplicand A having been shifted by one bit, wherein the multiplicand comprises an operand having at least 1024 bits, a second shift register configured to output the multiplicand A having been shifted by two bits, a 3× multiplier register configured to output 3 A, a first multiplexer having inputs coupled to a source of the multiplicand A, to the first shift register, to the second shift register, and to the 3× multiplier register and configured to output the multiplicand A, A<<1, A<<2, or 3 A, in response to a control signal based on a segment of a multiplier B, an inverter configured to generate a two's complement inversion of an output of the first multiplexer, a second multiplexer having inputs coupled to the output of the first multiplexer and to an output of the inverter and configured to output the multiplicand A, A<<1, A<<2, or 3 A, or a two's complement of A, A<<1, A<<2, or 3 A, or zero, in response to the control signal, and memory configured to store an output of the second multiplexer as an interstitial product.