Patent ID: 7783864

Claim:
A method for multiplying two multiplicands A and B each having up to n bits, modulo a number N having up to n bits, said method comprising: supplying partitioned portions of multiplicand A to respective processing elements m of a chain of processing elements, each partitioned portion having up to k bits, wherein n=m·k, each processing element being a hardware circuit operable to process k bits of multiplicand A; reserving a plurality of registers Z, wherein each of said registers Z corresponds to each of said processing elements; setting a value stored in said corresponding register Z to 0; for each of said processing elements: storing in temporary register X a result of a product of said processing element and B plus the value stored in said corresponding register Z; storing in another temporary register y a first partial product in a set of first subphases, said first partial product comprising a product of a constant and k least significant bits of said temporary register X modulo 2 K ; storing in said corresponding register Z of the subsequent processing element a second partial product of a set of second subphases comprising a product of said first partial product and N plus said result stored in temporary register X divided by 2 k ; each said hardware circuit being operable to simultaneously perform subphases of each of said sets of first and second subphases in each cycle of at least some cycles of said hardware circuit; operating said processing elements in a pipelined manner to simultaneously produce in each of said at least some cycles, said first partial products and said second partial products; passing said first partial products produced within said processing elements to at least one other processing element in said chain; passing said second partial products produced within said processing elements to at least one other processing element in said chain; and accumulating temporary results in a register set over sufficient number of operational cycles to produce a product of said multiplicands modulo said number N in said register set.