Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-03-30
2003-10-14
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S623000
Reexamination Certificate
active
06633896
ABSTRACT:
FIELD
The present invention relates to the field of computer systems, and more specifically to a method and system for multiplying large numbers on a computer system.
BACKGROUND
Many computer applications require the multiplication of large numbers. For example, some situations when such a need arises are when computers are used for processing or simulating scientific data, or executing a cryptographic system.
Cryptography systems may be used for scrambling private messages, for applying a crack-proof signature on an e-mail message, or for providing for secure online transactions. At their core, modern cryptography systems require two very large numbers, typically 1024 bit or larger, to be multiplied together. However, most modern computer microprocessors only have the native capability to multiply 32 or 64 bit numbers. Thus, software techniques are needed to multiply numbers greater than the processor's native capabilities.
Such software techniques govern the amount of time required by the microprocessor to multiply these large numbers. Thus, inadequate software techniques can negatively affect the system's performance. Moreover, as the use of e-commerce and other secure online transactions increase, there is a need for faster software multiplication techniques so that users can complete transactions quickly.
For the reasons stated above, and for other reasons stated below which will become apparent to those skilled in the art upon reading and understanding the present specification, there is a need in the art for a faster method for the multiplication of large numbers on a computer system.
SUMMARY
In one embodiment, a computer-implemented method for multiplying two large multiplicands includes generating a plurality of partial products by multiplying each digit of the first multiplicand with each digit of the second multiplicand and adding each of the most significant digits of each partial product to an appropriate location in a first array and adding each of the least significant digits of each partial product to an appropriate location in a second array. The method includes adding the first array to the second array, wherein the result is the product of the two original multiplicands. This and various other embodiments are described and claimed below.
REFERENCES:
patent: 4849923 (1989-07-01), Samudrala et al.
patent: 4979141 (1990-12-01), Gelinas et al.
patent: 5126963 (1992-06-01), Fukasawa
patent: 5144575 (1992-09-01), Jeong et al.
patent: 5276634 (1994-01-01), Suzuki et al.
patent: 5909385 (1999-06-01), Nishiyama et al.
patent: 5963461 (1999-10-01), Gorshtein et al.
Cetin et al., Analyzing and Comparing Montgomery Multiplication Algorithms, Jun. 1996, IEEE Micro, p. 26-33.*
Peter et al., An Area/Performance Comparision of Subtractive and Multiplicative Divide/Square Root Implementations, 1995, IEEE, p. 132-139.*
Sousa, F.M., et al., “The Computation of Extended-Precision Modular Arithmetic on a DSP Architechture”,PRoceedings of the Internationof Conference on Signal Processing Applications&Technology, 1603-1607, (1996).
Abraham Seth
Moore Stephen F.
Do Chat C.
Intel Corporation
Ngo Chuong Dinh
LandOfFree
Method and system for multiplying large numbers does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for multiplying large numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for multiplying large numbers will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3144291