Method and system for multiplying large numbers

Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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).

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFUS-PAI-O-3144291

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.