Patent ID: 7111166

Claim:
A microelectronic apparatus for performing {circle around (x)} multiplication and squaring in both polynomial based GF(2 q ) and GF(p) field arithmetic, squaring and reduction using a serial fed radix 2 l multiplier, B, with k character multiplicand segments, A i , and a k character ⊕ accumulator wherein reduction to a limited congruence is performed “on the fly”, in a systolic manner, with A i , a multiplicand, times B, a multiplier, over a modulus, N, and a result being at most 2k+1 characters long, including the k first emitting disregarded zero characters, which are not saved, where k characters have no less bits than the modulus, the apparatus comprising; a first (B), and second (N) main memory register means, each register operative to hold at least n bit long operands, respectively operative to store a multiplier value designated B, and a modulus, denoted N, wherein the modulus is smaller than 2 n ; a digital logic sensing detector, Y0, operative to anticipate “on the fly” when a modulus value is to be ⊕ added to the value in the ⊕ adder accumulator device such that all first k characters emitting from the device are forced to zero; a modular multiplying device for at least k character input multiplicands, with only one, at least k characters long ⊕ adder, ⊕ summation device operative to accept k character multiplicands, the {circle around (x)} multiplication device operative to switch into the ⊕ accumulator device, in turn, multiplicand values, and in turn to receive multiplier values from a B register, and an “on the fly” simultaneously generated anticipated value as a multiplier which is operative to force k first emitting zero output characters in the first phase, wherein at each effective machine cycle at least one designated multiplicand is ⊕ added into the ⊕ accumulation device; the multiplicand values to be switched in turn into the ⊕ accumulation device consisting of one or two of the following three multiplicands, a first multiplicand being an all-zero string value, a second multiplicand being the multiplicand A i , and a third multiplicand being the N 0 segment of the modulus; an apparatus to anticipate the l bit k character serial input Y 0 multiplier values; the multiplier values which are input in turn into the multiplying device in the first phase being first the B operand, and concurrently, the second multiplier value consisting of the Y 0 , “on the fly” anticipated k character string, to force first emitting zeroes in the output; an ⊕ accumulation device, operative to output values simultaneously as multiplicands are ⊕ added into the ⊕ accumulation device; an output transfer mechanism, in the second phase operative to output a final modular {circle around (x)} multiplication result from the ⊕ accumulation device, wherein all addition, accumulation and multiplication operations are switchable to be performed either with carries or without carries, over GF(p) or over GF(2 q ).