Method and apparatus for producing the residue of the product of two

Abstract

Method and apparatus for producing the residue of the product of a multiplier and a multiplicand where the multiplier, multiplicand and product are residues with respect to a check base m, and where m=(2.sup.b -1) and b is the number of bits in a residue. An addressable memory device has at least 2 2(b-1) memory locations with each memory location having an address of 2 (b-1) bits. The address of each memory location can be considered as having two components each of (b-1) bits. The residue stored at each addressable location of the device is the residue of the product of the two components of its address. In response to each address being applied to the memory device, the residue of the product of the two components stored at the addressed memory location is read out of the device. The lower order (b-1) bits of the multiplier is applied to the device if the most significant bit of the multiplier is a logical zero. If the most significant bit of the multiplier is a logical one, the complement of the lower order (b-1) bits is applied and forms one component of the address of a memory location of the device. Similarly, the value of the most significant bit of the multiplicand determines whether the lower order (b-1) bits of the multiplicand or their complements form the other component of the address applied to the memory device. The residue read out of the addressed location is complemented to produce the residue of the product stored at the addressed memory location if and only if one of the most significant bits of the multiplier and multiplicand is a logical one, otherwise the residue read out of the memory device is the residue of the product of the multiplier and the multiplicand.