Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-09-26
2004-06-08
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S491000
Reexamination Certificate
active
06748412
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention pertains generally to computers. In particular, it pertains to processing exponents electronically using an improved square-and-multiply technique.
2. Description of the Related Art
Several computer applications involve exponentiation, or the process of raising a base number to a power, where the exponent is a very large number. This is particularly true in some encryption/decryption schemes, such as the well-known Rivest-Shamir-Adleman (RSA) approach to public key encryption. The security of this system increases as the number of bits in the exponents increases. Current RSA implementations of public key encryption commonly use exponents with 1024 bits. As increasingly powerful computers become available for code-breaking efforts, the size of these numbers will most likely increase even more to maintain the same level of security.
The square-and-multiply technique has been developed to more efficiently process exponentiation when using binary numbers. In the conventional approach to this technique, each bit of the exponent is examined sequentially, starting with the most significant bit (MSB), and the current value of the process is operated on. Before starting, the base number (the number being raised to a power) represents the current value; after that, the result of the previous operation represents the current value. If the bit being examined in the exponent is a zero, the current value of the process is squared. If the bit being examined is a one, the current value of the process is both squared and multiplied by the original base number. The number of operations involved in this process equals the total number of bits in the exponent, plus the number of ‘1’ bits in the exponent, minus one. Thus, the average number of operations for a 1024-bit exponent would be 1535, assuming an equal number of ones and zeros in the average exponent. Since the base number typically involves large numbers in an encryption algorithm, each operation is a large and potentially time-consuming step if implemented in hardware, and even more time-consuming if implemented in software. The time to execute a conventional square-and-multiply approach increases linearly with the number of bits in the exponent, which can become a bottleneck in response times for those applications that use RSA encryption in interactive communications or other time-sensitive applications.
REFERENCES:
patent: 6240436 (2001-05-01), McGregor
patent: 6282290 (2001-08-01), Powell et al.
patent: 6434585 (2002-08-01), McGregor et al.
patent: 0 947 914 (1998-10-01), None
Knuth, Donald Ervin; The Art of Computer Programming; Mar. 2000, 6th Printing; pp. 461-464.
Walter C.D.; Exponentiation Using Division Chains; IEEE Transactions on Computers, IEEE Inc.; New York, U.S.; vol. 47, No. 7; Jul. 1, 1998, pp. 757-765.
LandOfFree
Square-and-multiply exponent processor does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Square-and-multiply exponent processor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Square-and-multiply exponent processor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3328495