Dual moduli exponent transform type high speed multiplication system

Claim 2

An asynchronous multiplier comprising: first means for calculating a first residue which is congruent with a result of a multiplication of a first and a second positive integer with respect to a first modulus which is equal to a prime number, both said first and said second positive integers being represented by an even number of digits; second means for calculating a first, a second, and a third product by multiplying (a) a lower half of the digits of said first positive integer by a lower half of the digits of said second positive integer, (b) the lower half of the digits of said first positive integer by the digits of a higher half of the second positive integer digits and (c) a higher half of the digits of said first positive integer by the lower half of the digits of said second positive integer, respectively; first combining means for combining said first through said third products into a second residue which is congruent with the result of the multiplication with respect to a second modulus which is equal to said prime number less one; and second combining means for combining said first and said second residues into said result of said multiplication.

Claim 3

The multiplier of claim 1 and means for giving a signal representative of each of said first and said second positive integers, said signal indicating said positive integers in terms of an optional numbering system.

Claim 4

A calculating system for calculating a result of a multiplication of a first and a second positive integer, each of said first and said second integers being related to a predetermined radix by a predetermined even number h of digits, said even number h being such that an h-th power of said radix plus one is a prime number, the calculation being carried out by a use of a first and a second residue, said first residue being congruent to said result of said multiplication with respect to a first modulus which is equal to said prime number less one, said second residue being congruent to said result of said multiplication with respect to a second modulus which is equal to said prime number, said result of said multiplication and each of said first and said second residues being related to said radix by 2h and h digits, respectively, said calculating system comprising: means including a subsystem for processing said first and said second positive integers into said second residue by a use of a fact known in the number theory in which consecutive integers are said prime number less one and are congruent to powers of a preselected primitive root of said prime number with respect to said second modulus, when exponents for the respective powers are given by consecutive whole numbers of said prime number less one; partial product calculating means for calculating a first, a second, and a third h-digit partial product by multiplying (a) a lower half of the digits of said first positive integer by a lower half of the digits of said second positive integer, (b) the lower half of the digits of said first positive integer by the digits of a higher half of the second positive integer digits, and (c) a higher half of the digits of said first positive integer by the lower half of the digits of said second positive integer, respectively; first combining means for combining said first through said third h-digit partial products into said first residue; and second combining means for combining said first and said second residues into said result of said multiplication.

Claim 5

A calculating system for calculating a result of a multiplication of a first and a second positive integer, each of said first and said second integers being related to a predetermined radix by a predetermined even number h of digits, said even number h being such that an h-th power of said radix plus one is a prime number, the calculation being carried out by a use of a first and a second residue, said first residue being congruent to said result of said multiplication with respect to a first modulus which is equal to said prime number less one, said second residue being congruent to said result of said multiplication with respect to a second modulus which is equal to said prime number, said result of said multiplication and each of said first and said second residues being related to said radix by 2h and h digits, respectively, said calculating system comprising: means including a subsystem for processing said first and said second positive integers into said second residue by a use of a fact known in the number theory in which consecutive integers are said prime number less one and are congruent to powers of a preselected primitive root of said prime number with respect to said second modulus, when exponents for the respective powers are given by consecutive whole numbers of said prime number less one; partial product calculating means for calculating a first, a second, and a third h-digit partial product by multiplying (a) a lower half of the digits of said first positive integer by a lower half of the digits of said second positive integer, (b) the lower half of the digits of said first positive integer by the digits of a higher half of the second positive integer digits, and (c) a higher half of the digits of said first positive integer by the lower half of the digits of said second positive integer, respectively; first combining means for combining said first through said third h-digit partial products into said first residue; and second combining means for combining said first and said second residues into said result of said multiplication.

Claim 6

The system of claim 3, wherein said subsystem means comprises: first transforming means for transforming said consecutive integers into said whole numbers; second transforming means for inversely transforming said whole numbers into said consecutive integers; means responsive to said first and said second positive integers for controlling said first transforming means to provide a first and a second of said whole numbers, respectively; means responsive to said first and said second whole numbers for calculating a sum residue which is congruent to a sum of said first and said second whole numbers with respect to first modulus; and means responsive to one of said whole numbers for controlling said second transforming means to provide one of said consecutive integers, said one whole number being equal to said calculated sum residue, the provided one of said consecutive integers giving said second residue.

Claim 7

The system of claim 3 or 4, wherein said second combining means comprises: processing means connected to said means including said subsystem and said first combining means for processing said first and said second residues into an h-digit processed result; and means connected to said processing means and said first combining means for concatenating said processed result and said first residue as higher and lower h digits of said result of said multiplication, respectively.

Claim 8

The system of claim 5, wherein said radix is "2" and the predetermined even number h is a predetermined one of the integers of "4", "8", and "16".

Claim 9

The system of claim 6, wherein: said partial product calculating means comprises: first partial product calculating means for multiplying the lower half of the first positive integer digits by the lower half of the second positive integer digits to separately provide a higher and a lower half of the digits of said first h-digit partial product; second partial product calculating means for multiplying the lower half of the first positive integer digits by the higher half of the second positive integer digits to separately provide a higher and a lower half of the digits of said second h-digit partial product; and third partial product calculating means for multiplying the higher half of the first positive integer digits by the lower half of the second positive integer digits to separately provide a higher and a lower half of the digits of said third h-digit partial product; said first combining merans comprising: summing means for summing the higher half of the first h-digit partial product digits, the lower half of the second h-digit partial product digits, and the lower half of the third h-digit partial product digits into an (h/2)-digit sum; and means for concatenating the lower half of the first h-digit partial product digits and said (h/2)-digit sum as higher and lower h/2 digits of said first residue, respectively.

Claim 10

The system of claim 5, wherein said radix is "10" and said predetermined even number is "2".