Multiplier with index transforms modulo a prime or modulo a fermat prime and the fermat prime less one

A multiplication system for calculating a product of two odd integers by a use of a first and a second modulus equal to a prime number m which is given by a Fermat number which is not less than five and equal to said prime number m less one, respectively, and by a use of a first and a second congruence relationship, said first congruence relationship being such that a first predetermined natural number raised to the power of consecutive whole numbers of a first group, (m-1)/2 in number, are congruent with those residues modulo of said prime number m which form a set of consecutive odd integers, when said residues are arranged in the ascending order, said first predetermined natural number being a primitive root inherent to said prime number m, said second congruence relationship being such that a negative unity raised to the powers 0 and 1 multiplied by a second predetermined natural number raised to the powers of consecutive whole numbers of a second group, (m-1)/4 in number, are congruent with those residues of said second modulus which form said set of consecutive odd integers when said second modulus is arranged in the ascending order, said second predetermined natural number being a quasi-primitive root inherent to said second modulus, whereby a one-to-one correspondence is established between said first-group of whole numbers and said consecutive odd integers according to said first congruence relationship and is established between combinations of 0 and 1 with said second group of whole numbers and said consecutive odd integers according to said second congruence relationship, said two odd integers being given as a first and a second of said consecutive odd integers, said second odd integer being enabled to be identical with said first odd integer, said multiplication system comprising:

• first transforming means for transforming said first and said second odd integers into a first and a second index of a first group, respectively, with said first and said second first-group indices being given by those two of said first group of whole numbers which are in a one-to-one correspondence with said first and said second odd integers, respectively, according to said first congruence relationship;
• first summing means responsive to said first and said second first-group indices for deriving a modulus sum of a first kind with which a sum of said first and said second first-group indices is congruent with respect to said second modulus;
• second transforming means for transforming said first kind of modulus sum into a first residue with said first residue being given by that one of said consecutive odd integers which is in a one-to-one correspondence with one of said first group of whole numbers according to said first congruence relationship, said one first group of whole numbers being given by said first kind of modulus sum;
• third transforming means for transforming said first odd integer into a first index of a first set and a first index of a second set, both of said sets being in a second group of indices, said third transforming means transforming said second odd integer into a second index of said first set and a second index of said second set, a first combination of said first first-set and said first second-set indices and a second combination of said second first-set and said second second-set indices being given by those two of said combinations of 0 and 1 with said second group of whole numbers which are in one-to-one correspondence with said first and said second odd integers, respectively, according to said second congruence relationship;
• second summing means responsive to said first and said second first-set indices for deriving a first modulus sum of a second kind with which a sum of said first and said second first-set indices is a congruent modulo two and responsive to said first and said second second-set indices for deriving a second modulus sum of said second kind with which a sum of said first and said second second-set indices is a congruent modulo (m-1)/4;
• fourth transforming means for transforming a combination of said first and said second second-kind of modulus sums into a second residue with said second residue being given by that one of said consecutive odd integers which is in a one-to-one correspondence with one of said combinations of 0 and 1 with said second group of whole numbers, said one combination being given by said combination of first and second second-kind modulus sums;
• and
• combining means for combining said first and said second residues into said product.

A multiplication system for calculating a product of two integers by a use of a first and a second modulus which is equal to a prime number m given by a Fermat number which is not less than five and is equal to said prime number m less one, respectively, and by a use of first and second congruence relationships, said first congruence relationship being such that a first predetermined natural number raised to the power of those consecutive whole numbers (which are (m-1)/2 in number) of a first group which are congruent with those residues modulo of said prime number m which form a set of consecutive odd integers, when the residues are arranged in the ascending order, said set of odd integers also being (m-1)/2 in number and being arranged in the ascending order, said first predetermined natural number being a primitive root which is inherent to said prime number m, said second congruence relationship being such that minus unity raised to the power of 0 and 1 multiplied by a second predetermined natural number raised to the power of (m- 1)/4 consecutive whole numbers of a second group, are congruent with those residues with respect to said second modulus which, when arranged in the ascending order, form said set of consecutive odd integers, said second predetermined natural number being a quasi-primitive root inherent to said second modulus, whereby a one-to-one correspondence is established between said first-group of whole numbers and said consecutive odd integers according to said first congruence relationship and between combinations of 0 and 1 with said second group of whole numbers and said consecutive odd integers according to said second congruence relationship, said two integers being given by a first and a second h-bit binary signal where h represents that exponent of the number "2" which represents said Fermat number as (2.sup.h +1), said multiplication system comprising:

• means responsive to said first and said second h-bit binary signals for producing a first and a second (h-1)-bit binary signal with the least significant bit being removed from each of said first and said second h-bit binary signals, said first and said second (h-1)-bit binary signals representing first and second odd integers when a binary "1" bit is added as a new least significant bit;
• first transforming means for transforming said first and said second (h-1)-bit binary signals into a first and a second index signal of a first group, respectively, each of said first and said second first-group index signals being of h binary bits, said first and said second first-group index signals being representative of a first and a second index of a first group, respectively, said first and said second first-group indices being those two of said first-group of whole numbers which are in a one-to-one correspondence with said first and said second odd integers, respectively, according to said first congruence relationship;
• first summing means responsive to said first and said second first-group of index signal for producing a modulus sum signal of a first kind of h binary bits, said first-kind of modulus sum signals being representative of a modulus sum of a first kind with which a sum of said first and said second first-group indices is congruent with respect to said second modulus;
• second transforming means for transforming said first kind of modulus sum signal into a first residue signal of h binary bits, said first residue signal being representative of a first residue given by that one of said consecutive odd integers which is in a one-to-one correspondence with one of said first group of whole numbers according to said first congruence relationship, said one first group of whole number being given by said first kind of modulus sum;
• third transforming means for transforming said first (h-1)-bit binary signal into a first combination of a first index signal of a first set and a first index signal of a second set, both sets being in a second group of index signals, and for transforming said second (h-1)-bit binary signal into a second combination of a second index signal of said first set and a second index signal of said second set, each of said first set of index signals being of single binary bits, each of said second-set index signals being of (h-2) binary bits, said first and said second first-set index signals being representative of a first and a second index of a first set, respectively, said first and said second second-set index signals being representative of a first and a second index of a second set, both sets of indices being in a second group of indices, said first combination of a first first-set and a first second-set indices and said second combination of a second first-set and a second second-set indices being given by those two of said combinations of 0 and 1 with said second group of whole numbers being in a one-to-one correspondence with said first and said second odd integers, respectively, according to said second congruence relationship;
• second summing means responsive to said first and said second first-set index signals for producing a first modulus sum signal of a second kind and responsive to said first and said second second-set index signals for producing a second modulus sum signal of said second kind, said first second-kind of modulus sum signal being a single binary bit and being representative of a first modulus sum of a second kind with which a sum of said first and said second first-set indices is a congruent modulo "2", said second second-kind of modulus sum signal being (h-2) binary bits and being representative of a second modulus sum of said second kind with which a sum of said first and said second second-set indices is congruent modulo (m-1)/4;
• fourth transforming means for transforming a combination of said first and said second second-kind of modulus sum signals to a second residue signal of h binary bits, said second residue signal being representative of a second residue given by that one of said consecutive odd integers which is in a one-to-one correspondence with one of said combination of 0 and 1 with said second group of whole numbers, said one combination being given by said combination of first and second second-kind of modulus sum;
• combining means for combining said first and said second residue signals into a resulting signal of 2h binary bits and being representative of a result of a multiplication of said first and said second odd integers;
• correction signal-producing means responsive to said first and said second h-bit binary signal for producing a correction signal representative of a correction integer which is equal to zero when each of two integers is odd, equal to the integer represented by said second h-bit binary signal when the integer represented by said first h-bit binary signal is even, equal to, the integer represented by said first h-bit binary when the integer represented by said second h-bit binary signal is even, and equal to a sum of said two integers, and unity, when the integer represented by said second h-bit binary signal is even, and each of said two integers is even;
• and
• adjusting means responsive to said resulting signal and said correction signal for producing a product signal of 2h binary bits and which is representative of said product with said product being given by subtracting said correction integer from said results of said multiplication.

A method of asynchronously multiplying two of a set of binary numbers representing a multiplicand and a multiplier, said method comprising the steps of:

• a. separately transforming each of the two numbers into non-logarithmic exponents which individually correspond to said two numbers, said transforms being accomplished by selectively addressing read-only memories storing tables of data representing sets of numbers including at least said two numbers;
• b. adding the non-logarithmic transform exponents;
• and
• c. transforming the sum of the added exponents back into said set of numbers by addressing another read-only memory containing tables of data representing a product of the multiplication in terms of said added exponents, said product being free of rounding errors.