Patent ID: 7805479

Claim:
A scalable electronic apparatus for residual modular multiplication comprising: a first register with capacity for storing and accessing at least 2 kmw+1 bit values; a second register with capacity for storing and accessing at least 2 kmw+1 bit values; a third and fourth register, each with capacity for storing and accessing at least 2 kmw bit values; a fifth register, with capacity for storing and accessing at least a w bit value; a carry-save adder whereby a carry-redundant representation of the sum of three multi-bit values and a single bit value can be computed; a plural multiplier unit whereby a w-bit input x and at least km separate w-bit inputs y i yield at least km 2w-bit outputs z i , each said 2w-bit output z i being the product of said w-bit input x and said w-bit input y i ; a two-input full adder, wherein each input comprises at least 2 kmw bits; a three-input full adder, wherein each input comprises at least w bits; a two-input w×w-bit multiplier; a w-input or gate; a control unit; wherein an input a is presented to the apparatus in 2 km words, an input b is presented to the apparatus in 2 km words, a modulus n is presented to the apparatus in 2 km words, the value n′ is presented to the apparatus in a single word, and the least and most significant bits of said modulus n are set to 1 further comprising: the first output of said carry-save adder routed to said first register; the second output of said carry-save adder routed to said second register; the output of said plural multiplier unit routed to said third register; the least significant 2 kmw bits of said first register and said second register routed to the two inputs of said two-input full adder; the least significant w bits of said first, second and third registers routed to said three-input w-bit full adder; the output of said three-input w-bit full adder and said input word n′ routed to the inputs of a w×w-bit multiplier; the least significant w bits of the output of said w×w-bit multiplier routed to said fifth register.