Modulo arithmetic processor chip

A modulo arithmetic processor chip for multiplying a first integer X by a second integer Z having a plurality of groups of bits, wherein the first integer X times the second integer Z equals a third integer Y having a plurality of groups of bits, modulo a fourth integer p having n-bits, whereby Y=X.multidot.Z mod p, comprising:

• first register means for storing the first integer X;
• second register means for storing the second integer Z;
• feedback means for generating a feedback number, F, wherein the feedback number F is the two's complement of the fourth integer p and thereby F=2.sup.n -p;
• first-partial-reduction means coupled to said second register means and responsive to the most significant position of the second integer Z shifted left from said second register means for adding the feedback number F to the second integer Z, thereby partially reducing the second integer Z;
• arithmetic means coupled to said first register means, and said second register means, and responsive to the least significant position of the first integer X shifted right from said first register means, for sequentially adding each group of bits of the second integer Z to a corresponding group of bits of the third integer Y during a time period, wherein each group of bits of the second integer Z and the corresponding group of bits of the third integer Y are added asynchronously during the time period;
• accumulator means coupled to said arithmetic means for storing the third integer Y;
• overflow means coupled to said accumulator means for counting and storing overflow bits as an overflow integer I;
• second-partial-reductions means coupled to said first register means, said second register means, said overflow means and said arithmetic means, and responsive to the completion of multiplying the first integer X by the second integer Z, for transferring the overflow integer I into said first register means, transferring the feedback number F into said second register means, multiplying feedback number F by the overflow integer I to generate a product, and adding the product to the third integer Y in said accumulator means;
• and
• means coupled to said accumulator means and responsive to the third integer Y being greater than the fourth integer p, for reducing third integer Y modulo the fourth integer p.

A modulo arithmetic processor chip for multiplying a first integer X by a second integer Z having a plurality of groups of bits, wherein the first integer X times the second integer Z equals a third integer Y having a plurality of groups of bits, modulo a fourth integer p having n-bits, whereby Y=X.multidot.Z mod p, comprising:

• first register means for storing the first integer X;
• second register means for storing the second integer Z;
• feedback means for generating a feedback number F, wherein the feedback number F is the two's complement of the fourth integer p and thereby F=2.sup.n -p;
• first-partial-reduction means coupled to said second register means and responsive to the most significant position of the second integer Z shifted left from said second register means, for adding the feedback number F to the second integer Z, thereby partially reducing the second integer Z;
• arithmetic means coupled to said first register means and said second register means, and responsive to the least significant position of the first integer X shifted right from said first register means, for sequentially adding each group of bits of the second integer Z to a corresponding group of bits of the third integer Y during a time period, wherein each group of bits of the second integer Z and the corresponding group of bits of the third integer Y are added asynchronously during the time period;
• accumulator means coupled to said arithmetic means for storing the third integer Y;
• overflow means coupled to said accumulator means for counting and storing overflow bits as an overflow integer I;
• second-partial-reduction means coupled to said overflow means, said feedback means, said first-register means and said second-register means, and responsive to the completion of multiplying the first integer X by the second integer Z, for transferring the overflow integer I into said first register means, transferring the feedback number F into said second register means, multiplying feedback number F by the overflow integer I to generate a product, and adding the product to the third integer Y in said accumulator means;
• and
• means coupled to said accumulator means and responsive to the third integer Y being greater than the fourth integer p, for reducing the third integer Y modulo the fourth integer p.

A modulo arithmetic processor chip for multiplying a first integer X by a second integer Z having a plurality of groups of bits, wherein the first integer X times the second integer Z equals a third integer Y having a plurality of groups of bits, modulo a fourth integer p having n-bits, whereby Y=X.multidot.Z mod p, comprising:

• first register means for storing the first integer X;
• second register means for storing the second integer Z;
• feedback means for generating and storing a feedback number F, wherein the feedback number F is the two's complement of the fourth integer p and thereby F=2.sup.n -p;
• first-partial-reduction means coupled to said second register means and responsive to the most significant position of the second integer Z shifted left from said second register means, for adding the feedback number F to the second integer Z, thereby partially reducing the second integer Z;
• arithmetic means coupled to said first register means and said second register means, and responsive to the least significant position of the first integer X shifted right from said first register means, for sequentially adding each group of bits of the second integer Z to a corresponding group of bits of the third integer Y during a time period, wherein each group of bits of the second integer Z and the corresponding group of bits of the third integer Y are added asynchronously during the time period;
• accumulator means coupled to said arithmetic means for storing the third integer Y;
• second-partial-reduction means coupled to said first register means, said second register means, said overflow means, said feedback means, and said arithmetic means, and responsive to the completion of multiplying the first integer X by the second integer Z, for transferring the overflow integer I into said first register means, transferring the feedback number F into said second register means, multiplying feedback number F by the overflow integer I to generate a product, and adding the product to the third integer Y in said accumulator means;
• and
• means coupled to said accumulator means and responsive to the third integer Y being greater than the fourth integer p, for reducing the third integer Y modulo the fourth integer p.

A method using a modulo arithmetic processor chip for adding a first integer X having having a plurality of groups of bits to a second integer Z having a plurality of groups of bits, wherein the first integer X plus the second integer Z equals a third integer Y having n-bits, modulo a fourth integer p having n-bits, whereby Y=(X+Z) mod p, comprising the steps, performed by said modulo arithmetic processor chip, of:

• storing the first integer X in first register means;
• storing the second integer Z in second register means;
• generating and storing a feedback number F in feedback means, wherein the feedback number F is the two's complement of the fourth integer p and thereby F=2.sup.n -p;
• generating the third integer Y by sequentially adding each group of bits of the first integer X to a corresponding group of bits of the second integer Z in arithmetic means during a time period, wherein each group of bits of the first integer A and a group of bits of the second integer Z are added asynchronously during the time period;
• storing the third integer Y in accumulator means which is coupled to said arithmetic means;
• storing an overflow integer in overflow means which is coupled to said accumulator means;
• fetching the feedback number F into said second register Z and adding the feedback number F using arithmetic means to the third integer Y in said accumulator means;
• and
• reducing the third integer Y modulo the fourth integer p in means coupled to the accumulator means, when the third integer Y is greater than the fourth integer p.

A method using a modulo arithmetic processor chip for multiplying a first integer X having n-bits by a second integer Z having a plurality of groups of bits, wherein the first integer X times the second integer Z equals a third integer Y having a plurality of groups of bits, modulo a fourth integer p having n-bits, whereby Y=X.multidot.Z mod p, comprising the steps, performed by said modulo arithmetic processor chip, of:

• storing the first integer X in first register means;
• storing the second integer Z in second register means;
• generating a feedback number F in feedback means, wherein the feedback number F is the two's complement, of the fourth integer p and thereby F=2.sup.n -p;
• adding the feedback number F to the second integer Z in response to the most significant position of the second integer Z shifted left from said second register means, thereby partially reducing the second integer Z;
• adding sequentially each group of bits of the second integer Z to a corresponding group of bits of the third integer Y in arithmetic means during a time period, wherein each group of bits of the first integer X and the corresponding group of bits of the second integer Z are added asynchronously during the time period in response to the least significant position of the first integer X shifted right from said first register means;
• storing the third integer Y in accumulator means;
• counting and storing overflow bits as an overflow integer I in overflow means;
• transferring the overflow integer I into said first register means, transferring the feedback number F into said second register means, and multiplying feedback number F by the overflow integer I to generate a product, and adding the product to the third integer Y in said accumulator means in second-partial-reductions means in response to the completion of multiplying the first integer X by the second integer Z;
• and
• reducing third integer Y modulo the fourth integer p in response to the third integer Y being greater than the fourth integer p.

A method using a modulo arithmetic processor chip for multiplying a first integer X having n-bits by a second integer Z having a plurality of groups of bits, wherein the first integer X times the second integer Z equals a third integer Y having a plurality of groups of bits, modulo a fourth integer p having n-bits, whereby Y=X.multidot.Z mod p, comprising the steps, performed by said modulo arithmetic processor chip, of:

• storing the first integer X in first register means;
• storing the second integer Z in second register means;
• generating a feedback number F in feedback means, wherein the feedback number F is the two's complement of the fourth integer p and thereby F=2.sup.n -p;
• adding sequentially in arithmetic means, in response to the least significant position of the first integer X shifted right from said first register means, group of bits of the second integer Z to corresponding group of bits of the third integer Y during a time period, wherein each group of bits of the second integer Z and the corresponding group of bits of the third integer Y are added asynchronously during the time period;
• storing the third integer Y in accumulator means;
• counting and storing overflow bits as an overflow integer I in overflow means;
• transferring the overflow integer I into said first register means, transferring the feedback number F into said second register means, and multiplying feedback number F by the overflow integer I to generate a product, and adding the product to the third integer Y in said accumulator means, in response to the completion of multiplying the first integer X by the second integer Z;
• and
• reducing the third integer Y modulo the fourth integer p in response to the third integer Y being greater than the fourth integer p.

A modulo arithmetic processor chip for multiplying a first integer X having n-bits by a second integer Z having a plurality of groups of bits, wherein the first integer X times the second integer Z equals a third integer Y having a plurality of groups of bits, modulo a fourth integer p having n-bits, whereby Y=X.multidot.Z mod p, comprising the steps, performed by said modulo arithmetic processor chip, of:

• storing the first integer X in first-register means;
• storing the second integer Z in second-register means;
• generating and storing a feedback number F in feedback means, wherein the feedback number F is the two's complement of the fourth integer p and thereby F=2.sup.n -p;
• adding the feedback number F to the second integer Z in response to the most significant position of the second integer Z shifted left from said second register means, thereby partially reducing the second integer Z;
• adding sequentially each group of bits of the second integer Z to a corresponding group of bits of the third integer Y in arithmetic means during a time period, wherein each group of bits in response to the least significant position of the first integer X shifted right from said first register means, the second integer Z and the corresponding group of bits of the third integer Y are added asynchronously during the time period;
• storing the third integer Y in accumulator means;
• and
• reducing the third integer Y modulo the fourth integer p in response to the third integer Y being greater than the fourth integer p.

A method using a modulo arithmetic processor chip for adding a first integer X having a plurality of groups of bits to a second integer Z having a plurality of groups of bits, wherein the first integer X plus the second integer Z equals a third integer Y having n-bits, modulo a fourth integer p having n-bits, whereby Y=(X+Z) mod p, comprising the steps, performed by said modulo arithmetic processor chip, of:

• storing the first integer X in first register means;
• storing the second integer Z in second register means;
• generating and storing a feedback number F in feedback means, wherein the feedback number F is the two's complement of the fourth integer p and thereby F=2.sup.n -p;
• generating the third integer Y by adding sequentially each group of bits of the first integer X to each group of bits the second integer Z during a time period, wherein each group of bits of the second integer Z and the corresponding group of bits of the third integer Y are added asynchronously during the time period;
• storing the third integer Y in accumulator means;
• storing an overflow integer in overflow means;
• fetching the feedback number F into said second register Z and adding the feedback number F to the third integer Y;
• and
• reducing the third integer Y modulo the fourth integer p, when the third integer Y is greater than the fourth integer p.