Device for and method of preforming an N-bit modular multiplicat

Details Device for and method of preforming an N-bit modular multiplicat Device for and method of preforming an N-bit modular multiplicat

1993-07-30

1994-09-20

Smith, Jerry

Boots, shoes, and leggings

364754, G06F 738, G06F 752

Patent

active

053495519

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.

REFERENCES:
patent: 5073870 (1991-12-01), Morita
patent: 5101431 (1992-03-01), Even
patent: 5144574 (1992-09-01), Morita
patent: 5289397 (1994-02-01), Clark et al.
C. K. Koc, C. Y. Hung, Carry-Save Adders for Computing the Product AB Modulo N. Jun. 21, 1990, pp. 899-900, Electronics Letters vol. 26 No. 13.
Forster, Dlay, Gorgui-Naguib, Carry Delayed Save Adders for Computing the Product A.B Modulo N in LOG.sub.2 N Steps, Aug. 30, 1990, pp. 1544-1545, Electronics Letters vol. 26, No. 18.
Takagi, A Radix-4 Modular Multiplication Hardware Algorithm for Modular Exponentiation, Aug. 1992, pp. 949-956, IEEE Transactions on Computers, vol. 41 No. 8.

Affiliated with

Also associated with

Rating

Device for and method of preforming an N-bit modular multiplicat does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Device for and method of preforming an N-bit modular multiplicat, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device for and method of preforming an N-bit modular multiplicat will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2430475