The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Sep. 20, 1994
Filed:
Jul. 30, 1993
John Petro, San Diego, CA (US);
Abstract
The present invention relates to a device for and a method of performing an n-bit modular multiplication of A.times.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.times.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.times.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.times.B modulo C.