Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2005-07-12
2005-07-12
Malzahn, D. H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06917956
ABSTRACT:
An improved apparatus and method for modular multiplication and exponentiation to achieve efficient computation involved in Montgomery multiplication is provided. Currently employed conventional iteration methods involve carry look-ahead additions. To overcome the time taken by carry look-ahead additions, there is thus provided, in accordance with a preferred embodiment of the present invention, an apparatus and method for separately storing and tracking the sum and the carry of the addition involved in Montgomery multiplication. In such a manner, the present invention achieves fast addition times since they are not dependent on the time to compute the carries. As a result, the iterations are carried out much faster than previously possible. By representing the value A in the Montgomery multiplication algorithm with a redundant notation, the sum and the carry of the addition are separately stored and tracked, thereby avoiding the delays involved in the computation of the carries. In such a manner, by separately storing and tracking the sum and the carry of the addition, this carry-save addition enables a much faster computation involved in Montgomery multiplication.
REFERENCES:
patent: 6151393 (2000-11-01), Jeong
patent: 6185596 (2001-02-01), Hadad et al.
patent: 6748410 (2004-06-01), Gressel et al.
By M. Moris Mano, California State University, Los Angeles “Computer System Architecture” 1976 by Prentice-Hall, Inc., Englewood Cliffs, N.J p. 242-249, Ch. 7, Sec. 7-3.
By Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone “Handbook of Applied Cryptography” 1997 by CRC Press LLC, Boca Raton, Florida p. 602-603 (14.33-14.41, 14.3.3); p. 619-620 (14.6, 14.92-14.96, 14.6.2).
Malzahn D. H.
Martine & Penilla & Gencarella LLP
Sun Microsystems Inc.
LandOfFree
Apparatus and method for efficient modular exponentiation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for efficient modular exponentiation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for efficient modular exponentiation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3378131