Modulo arithmetic processor chip

Claim 2

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, modulo a fourth integer p having n-bits, whereby Y=(X+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 n -p; arithmetic means coupled to said first register means and said second register means, for 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 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; accumulator means coupled to said arithmetic means for storing the third integer Y; overflow means coupled to said accumulator means for storing an overflow integer; means coupled to said overflow means and said second register means and responsive to the overflow integer, for 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 means coupled to the 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.

Claim 3

The modulo arithmetic processor chip as set forth in claim 1 wherein: said first register means includes a first plurality of registers; said second register means includes a second plurality of registers; and said arithmetic means includes a plurality of full adders coupled to said first plurality of registers and said second plurality of registers, for sequentially adding each group of bits of the first integer X to the corresponding group of bits of the second integer Z during a time period.

Claim 4

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

Claim 5

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

Claim 6

The modulo arithmetic processor chip as set forth in claim 3 wherein: said first register means includes a first plurality of registers; said second register means includes a second plurality of registers; and said arithmetic means includes a plurality of full adders coupled to said first plurality of registers and said second plurality of registers, for sequentially adding each group of bits of the second integer Z to the corresponding group of bits of the third integer Y during a time period.

Claim 7

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

Claim 8

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

Claim 9

The modulo arithmetic processor chip as set forth in claim 5 wherein: said first register means includes a first plurality of registers; said second register means includes a second plurality of registers; and said arithmetic means includes a plurality of full adders coupled to said first plurality of registers and said second plurality of registers, for sequentially adding the group of bits of the second integer Z to the corresponding group of bits of the third integer Y during a time period.

Claim 10

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

Claim 11

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

Claim 12

The modulo arithmetic processor chip as set forth in claim 7 wherein: said first register means includes a first plurality of registers; said second register means includes a second plurality of registers; and said arithmetic means includes a plurality of full adders coupled to said first plurality of registers and said second plurality of registers, for sequentially adding each group of bits of the second integer Z to the corresponding group of bits of the third integer Y during a time period.

Claim 19

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

Claim 20

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