Patent US5121431A successfully refreshed from Google Patents.
US5121431A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Processor method of multiplying large numbers
Assignee: Avaya Inc
•
Filing: 1990-07-02
•
Granted: 1992-06-09
•
Expires: 2010-07-02
Abstract
Abstract For a public key encryption system, for example using the RSA algorithm, large numbers, for example each of the order of 256 bits and represented by a plurality of sequentially stored words, must be multiplied together. To achieve this at high speed there is described a method using a digital signal processor which has two accumulators for accumulating products of words, each accumulator having a capacity of more than twice the size of the words which are multiplied. The two accumulators are used alternately for accumulating partial products of the same significance in a multiplication of two numbers. Pointers to the sequentially stored words are incremented in opposite directions to point to words to be multiplied to form partial products of the same significance, and the pointer incrementing directions are changed for sets of partial products of increasing significance. The pointer control and alternating use of the accumulators enables a significant increase in multiplication speed to be achieved.
Inventors
- 👤 Michael J. Wiener
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 21:20
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/38; G06F7/48; G06F7/52; G06F7/523; G06F7/53; G06F7/5324; G06F7/60; G06F7/72; G06F7/722
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
137 words
A method of multiplying two numbers, each represented by a plurality of words each of plurality of bits, in a processor comprising two accumulators, comprising the steps of: forming partial products in order of increasing significance by multiplying words of one number by words of the other number; accumulating partial products of like significance in an accumulator, the two accumulators being used alternately for consecutive accumulations of partial products of increasing significance; and between the consecutive accumulations of partial products using the two accumulators, deriving a word of a product of the two numbers from a lower order part of the most recently used accumulator, and transferring an accumulated number from a higher order part of that accumulator into a lower order part of the other accumulator for accumulation with the partial products of next higher significance.
Claim 2
Independent Claim
137 words
A method of multiplying two numbers, each represented by a plurality of words each of plurality of bits, in a processor comprising two accumulators, comprising the steps of: forming partial products in order of increasing significance by multiplying words of one number by words of the other number; accumulating partial products of like significance in an accumulator, the two accumulators being used alternately for consecutive accumulations of partial products of increasing significance; and between the consecutive accumulations of partial products using the two accumulators, deriving a word of a product of the two numbers from a lower order part of the most recently used accumulator, and transferring an accumulated number from a higher order part of that accumulator into a lower order part of the other accumulator for accumulation with the partial products of next higher significance.
Claim 3
Dependent Claim
27 words
A method as claimed in claim 1 wherein each of the two numbers being multiplied comprises at least about 256 bits in the words representing the number.
Claim 4
Dependent Claim
79 words
A method as claimed in claim 1 wherein for accommodating accumulated partial products each accumulator has a capacity greater than twice the size of each word, and the step of transferring an accumulated number from a higher order part of the most recently used accumulator into a lower order part of the other accumulator comprises transferring the accumulated number from two highest order parts of the most recently used accumulator into two lowest order parts of the other accumulator.
Claim 5
Dependent Claim
27 words
A method as claimed in claim 3 wherein each of the two numbers being multiplied comprises at least about 256 bits in the words representing the number.
Claim 6
Dependent Claim
88 words
A method as claimed in claim 3 wherein the words of each number are stored sequentially in memory, the method further comprising the steps of: for sets of accumulated partial products of like significance, incrementing first and second pointers in opposite directions to point to respective memory locations of words of the numbers to be multiplied together to form the respective partial products of like significance; and for consecutive accumulations of partial products of increasing significance, changing the directions in which the first and second pointers are incremented.
Claim 7
Dependent Claim
179 words
A method as claimed in claim 1 wherein for accommodating accumulated partial products each accumulator comprises a lowest order part for accommodating a lower order word, a higher order part for accommodating a higher order word, and a highest order part for accommodating carries from the higher order part, and the steps of deriving a word of a product and transferring an accumulated number comprise the steps, in sequence, of: storing the contents of the highest order part of the most recently used accumulator in the higher order part of the other accumulator and zeroing the remainder of said other accumulator; storing the contents of the higher order part of the most recently used accumulator in the lowest order part of the other accumulator and zeroing the higher order part of the most recently used accumulator; shifting the contents of the most recently used accumulator right by one bit; and shifting the contents of said other accumulator left by one bit, and deriving the word of the product from the lowest order part of the most recently used accumulator.
Claim 8
Dependent Claim
88 words
A method as claimed in claim 6 wherein the words of each number are stored sequentially in memory, the method further comprising the steps of: for sets of accumulated partial products of like significance, incrementing first and second pointers in opposite directions to point to respective memory locations of words of the numbers to be multiplied together to form the respective partial products of like significance; and for consecutive accumulations of partial products of increasing significance, changing the directions in which the first and second pointers are incremented.
Claim 9
Dependent Claim
88 words
A method as claimed in claim 1 wherein the words of each number are stored sequentially in memory, the method further comprising the steps of: for sets of accumulated partial products of like significance, incrementing first and second pointers in opposite directions to point to respective memory locations of words of the numbers to be multiplied together to form the respective partial products of like significance; and for consecutive accumulations of partial products of increasing significance, changing the directions in which the first and second pointers are incremented.
Claim 10
Independent Claim
114 words
A method of multiplying two numbers, each stored in memory as a plurality of sequential words each of a plurality of bits, in a processor by accumulating in order of increasing significance partial products formed by multiplying words of one number by words of the other number, comprising the steps of: for sets of accumulated partial products of like significance, incrementing first and second pointers in opposite directions to point to respective memory locations of words of the numbers to be multiplied together to form the respective partial products of like significance; and for consecutive accumulations of partial products of increasing significance, changing the directions in which the first and second pointers are incremented.
Claim 11
Independent Claim
114 words
A method of multiplying two numbers, each stored in memory as a plurality of sequential words each of a plurality of bits, in a processor by accumulating in order of increasing significance partial products formed by multiplying words of one number by words of the other number, comprising the steps of: for sets of accumulated partial products of like significance, incrementing first and second pointers in opposite directions to point to respective memory locations of words of the numbers to be multiplied together to form the respective partial products of like significance; and for consecutive accumulations of partial products of increasing significance, changing the directions in which the first and second pointers are incremented.
Claim 12
Independent Claim
251 words
A method of multiplying a first number X, comprising m words X1 to Xm in order of increasing significance, and a second number Y, comprising n words Y1 to Yn in order of increasing significance, where m and n are integers greater than one, to form a product R comprising m+n words R1 to Rm+n in order of increasing significance, using a processor comprising two accumulators each having a capacity greater than twice the size of each word, comprising the steps of: in consecutive steps i where i is an integer from 1 to m+n-1: selecting one of the accumulators when i is odd and the other of the accumulators when i is even; and forming and accumulating in the selected accumulator all of the products Xj*Yk, where j is an integer from 1 to m, k is an integer from 1 to n, and j+k=i+1, in order of decreasing j when i is odd and in order of increasing j when i is even; following each of the steps for which i<m+n-1: deriving a word Ri of the product R from a lower order part of the selected accumulator; and storing an accumulated number from a higher order part of the selected accumulator in a lower order part of the other accumulator for accumulation with products for the next value of i; and, following the step for which i=m+n-1: deriving the words Rm+n and Ri of the product R from respectively higher and lower order parts of the selected accumulator.
Claim 13
Independent Claim
251 words
A method of multiplying a first number X, comprising m words X1 to Xm in order of increasing significance, and a second number Y, comprising n words Y1 to Yn in order of increasing significance, where m and n are integers greater than one, to form a product R comprising m+n words R1 to Rm+n in order of increasing significance, using a processor comprising two accumulators each having a capacity greater than twice the size of each word, comprising the steps of: in consecutive steps i where i is an integer from 1 to m+n-1: selecting one of the accumulators when i is odd and the other of the accumulators when i is even; and forming and accumulating in the selected accumulator all of the products Xj*Yk, where j is an integer from 1 to m, k is an integer from 1 to n, and j+k=i+1, in order of decreasing j when i is odd and in order of increasing j when i is even; following each of the steps for which i<m+n-1: deriving a word Ri of the product R from a lower order part of the selected accumulator; and storing an accumulated number from a higher order part of the selected accumulator in a lower order part of the other accumulator for accumulation with products for the next value of i; and, following the step for which i=m+n-1: deriving the words Rm+n and Ri of the product R from respectively higher and lower order parts of the selected accumulator.
Claim 14
Dependent Claim
46 words
A method as claimed in claim 10 wherein each step of deriving a word Ri of the product R from a lower order part of the selected accumulator comprises shifting the word in the lower order part of the selected accumulator right by one bit position.
Claim 15
Dependent Claim
53 words
A method as claimed in claim 11 wherein each step of storing an accumulated number from a higher order part of the selected accumulator in a lower order part of the other accumulator for accumulation with products for the next value of i comprises shifting the accumulated number left by one bit position.
Claim 16
Dependent Claim
184 words
A method as claimed in claim 10 wherein each accumulator comprises a lowest order part for accommodating a lower order word, a higher order part for accommodating a higher order word, and a highest order part for accommodating carries from the higher order part, and the steps of deriving a word Ri of the product R and storing an accumulated number from a higher order part of the selected accumulator in a lower order part of the other accumulator comprise the steps, in sequence, of: storing the contents of the highest order part of the selected accumulator in the higher order part of the other accumulator and zeroing the remainder of said other accumulator; storing the contents of the higher order part of the selected accumulator in the lowest order part of the other accumulator and zeroing the higher order part of the selected accumulator; shifting the contents of the selected accumulator right by one bit; and shifting the contents of said other accumulator left by one bit, and deriving the word of the product from the lowest order part of the selected accumulator.
Claim 17
Dependent Claim
17 words
A method as claimed in claim 13 wherein the processor comprises a Motorola DSP56000 digital signal processor.
Claim 18
Dependent Claim
11 words
A method as claimed in claim 13 wherein m=12 and n=12.
Claim 19
Dependent Claim
9 words
A method as claimed in claim 10 wherein m=n.
Claim 20
Independent Claim
143 words
A method of coding information comprising multiplying two numbers, each represented by a plurality of words each of a plurality of bits, in a processor comprising two accumulators, the multiplication comprising the steps of: forming partial products in order of increasing significance by multiplying words of one number by words of the other number; accumulating partial products of like significance in an accumulator, the two accumulators being used alternately for consecutive accumulations of partial products of increasing significance; and between the consecutive accumulations of partial products using the two accumulators, deriving a word of a product of the two numbers from a lower order part of the most recently used accumulator, and transferring an accumulated number from a higher order part of that accumulator into a lower order part of the other accumulator for accumulation with the partial products of next higher significance.
Claim 21
Independent Claim
143 words
A method of coding information comprising multiplying two numbers, each represented by a plurality of words each of a plurality of bits, in a processor comprising two accumulators, the multiplication comprising the steps of: forming partial products in order of increasing significance by multiplying words of one number by words of the other number; accumulating partial products of like significance in an accumulator, the two accumulators being used alternately for consecutive accumulations of partial products of increasing significance; and between the consecutive accumulations of partial products using the two accumulators, deriving a word of a product of the two numbers from a lower order part of the most recently used accumulator, and transferring an accumulated number from a higher order part of that accumulator into a lower order part of the other accumulator for accumulation with the partial products of next higher significance.
Claim 22
Independent Claim
119 words
A method of coding information comprising multiplying two numbers, each stored in memory as a plurality of sequential words each of a plurality of bits, in a processor by accumulating in order of increasing significance partial products formed by multiplying words of one number by words of the other number, the multiplication comprising the steps of: for sets of accumulated partial products of like significance, incrementing first and second pointers in opposite directions to point to respective memory locations of words of the numbers to be multiplied together to form the respective partial products of like significance; and for consecutive accumulations of partial products of increasing significance, changing the directions in which the first and second pointers are incremented.
Claim 23
Independent Claim
119 words
A method of coding information comprising multiplying two numbers, each stored in memory as a plurality of sequential words each of a plurality of bits, in a processor by accumulating in order of increasing significance partial products formed by multiplying words of one number by words of the other number, the multiplication comprising the steps of: for sets of accumulated partial products of like significance, incrementing first and second pointers in opposite directions to point to respective memory locations of words of the numbers to be multiplied together to form the respective partial products of like significance; and for consecutive accumulations of partial products of increasing significance, changing the directions in which the first and second pointers are incremented.
Claim 24
Independent Claim
256 words
A method of coding information comprising multiplying a first number X, comprising m words X1 to Xm in order of increasing significance, and a second number Y, comprising n words Y1 to Yn in order of increasing significance, where m and n are integers greater than one, to form a product R comprising m+n words R1 to Rm+n in order of increasing significance, using a processor comprising two accumulators each having a capacity greater than twice the size of each word, the multiplication comprising the steps of: in consecutive steps i where i is an integer from 1 to m+n-1: selecting one of the accumulators when i is odd and the other of the accumulators when i is even; and forming and accumulating in the selected accumulator all of the products Xj*Yk, where j is an integer from 1 to m, k is an integer from 1 to n, and j+k=i+1, in order of decreasing j when i is odd and in order of increasing j when i is even; following each of the steps for which i<m+n-1: deriving a word Ri of the product R from a lower order part of the selected accumulator; and storing an accumulated number from a higher order part of the selected accumulator in a lower order part of the other accumulator for accumulation with products for the next value of i; and, following the step for which i=m+n-1: deriving the words Rm+n and Ri of the product R from respectively higher and lower order parts of the selected accumulator.
Claim 25
Independent Claim
256 words
A method of coding information comprising multiplying a first number X, comprising m words X1 to Xm in order of increasing significance, and a second number Y, comprising n words Y1 to Yn in order of increasing significance, where m and n are integers greater than one, to form a product R comprising m+n words R1 to Rm+n in order of increasing significance, using a processor comprising two accumulators each having a capacity greater than twice the size of each word, the multiplication comprising the steps of: in consecutive steps i where i is an integer from 1 to m+n-1: selecting one of the accumulators when i is odd and the other of the accumulators when i is even; and forming and accumulating in the selected accumulator all of the products Xj*Yk, where j is an integer from 1 to m, k is an integer from 1 to n, and j+k=i+1, in order of decreasing j when i is odd and in order of increasing j when i is even; following each of the steps for which i<m+n-1: deriving a word Ri of the product R from a lower order part of the selected accumulator; and storing an accumulated number from a higher order part of the selected accumulator in a lower order part of the other accumulator for accumulation with products for the next value of i; and, following the step for which i=m+n-1: deriving the words Rm+n and Ri of the product R from respectively higher and lower order parts of the selected accumulator.
References Cited (Backward Citations)
US4831577A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-06-09 | 1995-12-09 | 1996-06-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-06-09 | 1999-12-09 | 2000-06-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-06-09 | 2003-12-09 | 2004-06-09 | $7700.00 | Window Closed / Lapsed |