Device for and method of preforming an N-bit modular multiplication in approximately N/2 steps - 5349551









The present invention relates to a device for and a method of performing an n-bit modular multiplication of A×B modulo C in approximately n/2 steps, where A denotes a binary multiplier, B denotes a binary multiplicand, and C denotes a binary modulus. A, B, and -C are stored in registers. All variables needed to perform the A×B modulo C are generated. A partial product register is initialized. The multiplier A is scanned two bits at a time. The value of these two bits determines the multiple of B added to the partial product register. The values 4C, 2C, and C are subtracted from the partial product. If any of these subtractions result in a negative number the result of that subtraction is discarded. The partial product is then shifted two significant positions and stored in the partial product register. These steps are repeated until every bit of A has been scanned. The partial product is then converted to non-redundant form. The value C is then subtracted from the partial product. If the result of this subtraction is positive the result is transmitted as A×B modulo C. Otherwise the result of this last subtraction is discarded and the partial product existing just prior to this last subtraction is transmitted as A×B modulo C.Device for and method of preforming an N-bit modular multiplication in approximately N/2 steps534955120/09/199430/07/19931994417Petro; JohnUS Patent and Trademark OfficeGoogle Patent Searchpatentimages.storage.googleapis.com/pages/US5349551-1.pngUniquepartial productpartial product registermoduloresultbitslast subtractionsubtractionvaluestepsn-bit modular multiplication