Patent ID: 7111032

Claim:
A residue computing device on a Galois Field GF(2^m), for calculating a residue R of a product of a multiplier factor X and a multiplicand Y under a modulo Z, comprising: a gate G 1 for allowing the multiplier factor X to pass therethrough when a leading bit MSB of the multiplicand Y is 1; an adder ADD for adding a temporary residue R′ and a value obtained by said passage to provide a summed value SUM; a gate G 2 for allowing the modulo Z to pass therethrough when a leading bit MSB of the summed value SUM is 1; and a subtractor SUB for subtracting the modulo Z passed through the gate G 2 from the summed value SUM, to provide a subtracted value, wherein a value obtained by shifting the subtracted value of the subtractor by one bit is set as the temporary residue R′ for a next clock, wherein the shifting is repeatedly performed for each clock to thereby provide a subtracted value from the subtractor SUB as the residue R.