Modulo arithmetic processor chip

Claim 5

Apparatus according to claim 2, further comprising: a feedback register having L-bits for storing an n-bit feedback number; means for generating a feedback number from the integer number, p, having n-bits and storing the feedback number in the feedback register; and modulo means coupled to said feedback register and said first and second C register for reducing data bits stored in said first and second C registers modulo the integer number p.

Claim 6

Apparatus according to claim 1, further comprising: means for computing exponentiation in the ring of integers modulo an integer number p from a series of multiplications modulo p according to X Z = X Z[0] {X Z[1] {X Z[2] ...{X² ) Z[m-1] }²}²

Claim 7

Apparatus according to any one of claims 1 to 3, further comprising: comprising: an overflow counter coupled to full adder for counting overflows, I, from said full counter; and wherein said full adder adds I2 n to to said first and second C registers by replacing 2 n by the feedback number F₁ and adding IF₁ to the accumulator registers.

Claim 8

A modulo arithmetic processor chip for adding a first integer A having n-bits to a second integer B having n-bits, wherein the first integer A plus the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, and wherein the first integer A is represented by the binary numbers {A[i]} in the form A = A[n-1]2 n-1 + A[n-2]2 n-2 + A[n-3]2 n-3 + ... + A[1]2 + A[0], the second integer B is represented by the binary numbers {B[i]} in the form B = B[n-1]2 n-1 + B[n-2]2 n-2 + B[n-3]2 n-3 + ... + B[1]2 + B[0], the third integer C is represented by the binary numbers {C[i]} in the form C = C[n-1]2 n-1 + C[n-2]2 n-2 + C[n-3]2 n-3 + ... + C[1]2 + C[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p = [n-1]2 n-1 + P[n-2]2 n-2 - P[n-3]2 n-3 + ... + P[1]2 + P[0], whereby C = (A + B) mod p, comprising; first register means for storing the first integer A; second register means for storing the second integer B 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 C from adding the first integer A to the second integer B; accumulator means coupled to said arithmetic means for storing the third integer C; 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 B and adding the feedback number F using arithmetic means to the third integer C in said accumulator means; and means coupled to the accumulator means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 9

A modulo arithmetic processor chip for adding a first integer A having n-bits to a second integer B having n-bits, wherein the first integer A plus the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, and wherein the first integer A is represented by the binary numbers {A[i]} in the form A = A[n-1]2 n-1 + A[n-2]2 n-2 + A[n-3]2 n-3 + ... + A[1]2 + A[0], the second integer B is represented by the binary numbers {B[i]} in the form B = B[n-1]2 n-1 + B[n-2]2 n-2 + B[n-3]2 n-3 + ... + B[1]2 + B[0], the third integer C is represented by the binary numbers {C[i]} in the form C = C[n-1]2 n-1 + C[n-2]2 n-2 + C[n-3]2 n-3 + ... + C[1]2 + C[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p = [n-1]2 n-1 + P[n-2]2 n-2 - P[n-3]2 n-3 + ... + P[1]2 + P[0], whereby C = (A + B) mod p, comprising; first register means for storing the first integer A; second register means for storing the second integer B 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 C from adding the first integer A to the second integer B; accumulator means coupled to said arithmetic means for storing the third integer C; 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 B and adding the feedback number F using arithmetic means to the third integer C in said accumulator means; and means coupled to the accumulator means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 10

A modulo arithmetic processor chip according to claim 6 wherein said arithmetic means includes a plurality of full adders coupled to said first register means and said second register means, for adding the first integer A to the second integer B.

Claim 11

A modulo arithmetic processor chip according to claim 6 wherein said arithmetic means includes a plurality of half adders coupled to said first register means and said second register means, for adding the first integer A to the second integer B.

Claim 12

A modulo arithmetic processor chip for adding a first integer A having n-bits to a second integer B having n-bits, wherein the first integer A plus the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, and wherein base bits of the first integer A are represented by the binary numbers {A₁[i]} in the form A₁ = A₁[n-1]2 n-1 + A₁[n-2]2 n-2 + A₁[n-3]2 n-3 + ... + A₁[1]2 + A₁[0], carry bits of the first integer A are represented by the binary numbers {A₂[i]} in the form A₂ = A₂[n-1]2 n-1 + A₂[n-2]2 n-2 + A₂[n-3]2 n-3 + ... + A₂[1]2 + A₂[0], base bits of the second integer B are represented by the binary numbers {B₁[i]} in the form B₁ = B₁[n-1]2 n-1 + B₁[n-2]2 n-2 +B₁[n-3]2 n-3 + ... + B₁[1]2 + B₁[0], carry bits of the second integer B are represented by the binary numbers {B₂[i]} in the form B₂ = B₂[n-1]2 n-1 + B₂[n-2]2 n-2 + B₂[n-3]2 n-3 + ... + B₂[1]2 + B₂[0], base bits of the third integer C are represented by the binary numbers {C₁[i]} in the form C₁ = C₁[n-1]2 n-1 + C₁[n-2]2 n-2 + C₁[n-3]2 n-3 + ... + C₁[n-2]2 + C₁[0], carry bits of the third integer C are represented by the binary numbers {C₂[i] in the form C₂ = C₂[n-1]2 n-1 + C₂[n-2]2 n-2 +C₂[n-3]2 n-3 + ... + C₂[n-2]2 + C₂[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p = P[n-1]2 n-1 + P[n-2]2 n-2 + P[n-3]2 n-3 + ... + P[1]2 + P[0], whereby C = (A + B) mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base bits of the second integer B; second-carry-register means for storing the carry bits of the second integer B; feedback means for generating a first feedback number F₁, a second feedback number F₂, a third feedback number F₃, and a fourth feedback number F₄, wherein the first feedback number F₁ is the two's complement of the fourth integer p and thereby F₁ = 2 n - p, the second feedback number F₂ equals two times the first feedback number F₁ and thereby F₂ = 2F₁ mod p, the third feedback number F₃ equals three times the first feedback number F₁ and thereby F₃ = 3F₁ mod p, and the fourth feedback number F₄ equals four times the first feedback number F₁ and thereby F₄ = 4F₁ mod p; arithmetic means having a plurality of full adders, coupled to said first-base-register means, said first-carry-register means, said second-base-register means, and said second-carry-register means, for simultaneously adding with said plurality of full adders the base bits and carry bits of the first integer A to the respective base bits of the second integer B to generate a first sum having base bits and carry bits, and subsequently adding with said plurality of full adders the base bits and carry bits of the first sum to the respective carry bits of the second integer B to generate the base bits and the carry bits of the third integer C, respectively; accumulator-base means coupled to said arithmetic means for storing the base bits of the third integer C; accumulator-carry means coupled to said arithmetic means for storing the carry bits of the third integer C; overflow means coupled to said accumulator base means and said accumulator carry means for counting and storing overflow bits as an overflow integer I; means coupled to said overflow means, said second-base-register means, and said feedback means, and responsive to the overflow integer I = 1, 2, 3, or 4, for fetching the feedback number F₁, F₂, F₃, or F₄, respectively, from said feedback means into said second-base-register means and adding the feedback number F₁, F₂, F₃, or F₄, respectively, using arithmetic means to the third integer C in said accumulator-base means and said accumulator-carry means; and means coupled to the accumulator-base means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 13

A modulo arithmetic processor chip for adding a first integer A having n-bits to a second integer B having n-bits, wherein the first integer A plus the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, and wherein base bits of the first integer A are represented by the binary numbers {A₁[i]} in the form A₁ = A₁[n-1]2 n-1 + A₁[n-2]2 n-2 + A₁[n-3]2 n-3 + ... + A₁[1]2 + A₁[0], carry bits of the first integer A are represented by the binary numbers {A₂[i]} in the form A₂ = A₂[n-1]2 n-1 + A₂[n-2]2 n-2 + A₂[n-3]2 n-3 + ... + A₂[1]2 + A₂[0], base bits of the second integer B are represented by the binary numbers {B₁[i]} in the form B₁ = B₁[n-1]2 n-1 + B₁[n-2]2 n-2 +B₁[n-3]2 n-3 + ... + B₁[1]2 + B₁[0], carry bits of the second integer B are represented by the binary numbers {B₂[i]} in the form B₂ = B₂[n-1]2 n-1 + B₂[n-2]2 n-2 + B₂[n-3]2 n-3 + ... + B₂[1]2 + B₂[0], base bits of the third integer C are represented by the binary numbers {C₁[i]} in the form C₁ = C₁[n-1]2 n-1 + C₁[n-2]2 n-2 + C₁[n-3]2 n-3 + ... + C₁[n-2]2 + C₁[0], carry bits of the third integer C are represented by the binary numbers {C₂[i] in the form C₂ = C₂[n-1]2 n-1 + C₂[n-2]2 n-2 +C₂[n-3]2 n-3 + ... + C₂[n-2]2 + C₂[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p = P[n-1]2 n-1 + P[n-2]2 n-2 + P[n-3]2 n-3 + ... + P[1]2 + P[0], whereby C = (A + B) mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base bits of the second integer B; second-carry-register means for storing the carry bits of the second integer B; feedback means for generating a first feedback number F₁, a second feedback number F₂, a third feedback number F₃, and a fourth feedback number F₄, wherein the first feedback number F₁ is the two's complement of the fourth integer p and thereby F₁ = 2 n - p, the second feedback number F₂ equals two times the first feedback number F₁ and thereby F₂ = 2F₁ mod p, the third feedback number F₃ equals three times the first feedback number F₁ and thereby F₃ = 3F₁ mod p, and the fourth feedback number F₄ equals four times the first feedback number F₁ and thereby F₄ = 4F₁ mod p; arithmetic means having a plurality of full adders, coupled to said first-base-register means, said first-carry-register means, said second-base-register means, and said second-carry-register means, for simultaneously adding with said plurality of full adders the base bits and carry bits of the first integer A to the respective base bits of the second integer B to generate a first sum having base bits and carry bits, and subsequently adding with said plurality of full adders the base bits and carry bits of the first sum to the respective carry bits of the second integer B to generate the base bits and the carry bits of the third integer C, respectively; accumulator-base means coupled to said arithmetic means for storing the base bits of the third integer C; accumulator-carry means coupled to said arithmetic means for storing the carry bits of the third integer C; overflow means coupled to said accumulator base means and said accumulator carry means for counting and storing overflow bits as an overflow integer I; means coupled to said overflow means, said second-base-register means, and said feedback means, and responsive to the overflow integer I = 1, 2, 3, or 4, for fetching the feedback number F₁, F₂, F₃, or F₄, respectively, from said feedback means into said second-base-register means and adding the feedback number F₁, F₂, F₃, or F₄, respectively, using arithmetic means to the third integer C in said accumulator-base means and said accumulator-carry means; and means coupled to the accumulator-base means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 14

A modulo arithmetic processor chip for adding a first integer A having n-bits to a second integer B having n-bits, wherein the first integer A plus the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, and wherein base bits of the first integer A are represented by the binary numbers {A₁[i]} in the form A₁ = A₁[n-1]2 n-1 + A₁[n-2]2 n-2 + A₁[n-3]2 n-3 + ... + A₁[1]2 + A₁[0], carry bits of the first integer A are represented by the binary numbers {A₂[i]} in the form A₂ = A₂[n-1]2 n-1 + A₂[n-2]2 n-2 + A₂[n-3]2 n-3 + ... + A₂[1]2 + A₂[0], base bits of the second integer B are represented by the binary numbers {B₁[i]} in the form B₁ = B₁[n-1]2 n-1 + B₁[n-2]2 n-2 + B₁[n-3]2 n-3 + ... + B₁[1]2 + B₁[0], carry bits of the second integer B are represented by the binary numbers {B₂[i]} in the form B₂ = B₂[n-1]2 n-1 + B₂[n-2]2 n-2 + B₂[n-3]2 n-3 + ... + B₂[1]2 + B₂[0], base bits of the third integer C are represented by the binary numbers {C₁[i]} in the form C₁ = C₁[n-1]2 n-1 + C₁[n-2]2 n-2 + C₁[n-3]2 n-3 + ... + C₁[n-2]2 + C₁[0], carry bits of the third integer C are represented by the binary numbers {C₂[i]} in the form C₂ = C₂[n-1]2 n-1 + C₂[n-2]2 n-2 + C₂[n-3]2 n-3 + ... + C₂[n-2]2 + C₂[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p = P[n-1]2 n-1 + P[n-2]2 n-2 + P[n-3]2n n-3 + ... + P[1]2 + P[0], whereby C = (A + B) mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base bits of the second integer B; second-carry-register means for storing the carry bits of the second integer B; 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; arithmetic means coupled to said first-base-register means, said first-carry-register means, said second-base-register means, and said second-carry-register means, for simultaneously adding the base bits and carry bits of the first integer A to the respective base iits of the second integer B to generate a first sum having base bits and carry bits, and subsequently adding the base bits and carry bits of the first sum to the respective carry bits of the second integer B to generate the base bits and carry bits of the third integer C, respectively; accumulator-base means coupled to said arithmetic means for storing the base bits of the third integer C; accumulator-carry means coupled to said arithmetic means for storing the carry bits of the third integer C; overflow means coupled to said accumulator base means and said accumulator carry means for counting and storing overflow bits as an overflow integer I; means coupled to said overflow means, said second-base-register means, and said feedback means, and responsive to the overflow integer, for fetching the feedback number F from said feedback means and adding the feedback number F to the third integer C; and means coupled to said accumulator-base means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 15

A modulo arithmetic processor chip for adding a first integer A having n-bits to a second integer B having n-bits, wherein the first integer A plus the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, and wherein base bits of the first integer A are represented by the binary numbers {A₁[i]} in the form A₁ = A₁[n-1]2 n-1 + A₁[n-2]2 n-2 + A₁[n-3]2 n-3 + ... + A₁[1]2 + A₁[0], carry bits of the first integer A are represented by the binary numbers {A₂[i]} in the form A₂ = A₂[n-1]2 n-1 + A₂[n-2]2 n-2 + A₂[n-3]2 n-3 + ... + A₂[1]2 + A₂[0], base bits of the second integer B are represented by the binary numbers {B₁[i]} in the form B₁ = B₁[n-1]2 n-1 + B₁[n-2]2 n-2 + B₁[n-3]2 n-3 + ... + B₁[1]2 + B₁[0], carry bits of the second integer B are represented by the binary numbers {B₂[i]} in the form B₂ = B₂[n-1]2 n-1 + B₂[n-2]2 n-2 + B₂[n-3]2 n-3 + ... + B₂[1]2 + B₂[0], base bits of the third integer C are represented by the binary numbers {C₁[i]} in the form C₁ = C₁[n-1]2 n-1 + C₁[n-2]2 n-2 + C₁[n-3]2 n-3 + ... + C₁[n-2]2 + C₁[0], carry bits of the third integer C are represented by the binary numbers {C₂[i]} in the form C₂ = C₂[n-1]2 n-1 + C₂[n-2]2 n-2 + C₂[n-3]2 n-3 + ... + C₂[n-2]2 + C₂[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p = P[n-1]2 n-1 + P[n-2]2 n-2 + P[n-3]2n n-3 + ... + P[1]2 + P[0], whereby C = (A + B) mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base bits of the second integer B; second-carry-register means for storing the carry bits of the second integer B; 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; arithmetic means coupled to said first-base-register means, said first-carry-register means, said second-base-register means, and said second-carry-register means, for simultaneously adding the base bits and carry bits of the first integer A to the respective base iits of the second integer B to generate a first sum having base bits and carry bits, and subsequently adding the base bits and carry bits of the first sum to the respective carry bits of the second integer B to generate the base bits and carry bits of the third integer C, respectively; accumulator-base means coupled to said arithmetic means for storing the base bits of the third integer C; accumulator-carry means coupled to said arithmetic means for storing the carry bits of the third integer C; overflow means coupled to said accumulator base means and said accumulator carry means for counting and storing overflow bits as an overflow integer I; means coupled to said overflow means, said second-base-register means, and said feedback means, and responsive to the overflow integer, for fetching the feedback number F from said feedback means and adding the feedback number F to the third integer C; and means coupled to said accumulator-base means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 16

A modulo arithmetic processor chip according to claim 10 wherein said arithmetic means includes a plurality of full adders coupled to said first-base-register means, said first-carry-register means, said second-base register means and said second-carry-register means, for simultaneously adding the base bits and carry bits of the first integer A to the respective base bits of the second integer B to generate a first sum having base bits and carry bits, and storing the base bits and carry bits of the first sum in said base accumulator means and said carry accumulator means, respectively.

Claim 17

A modulo arithmetic processor chip according to claim 11 further including multiplex means coupled to said plurality of full adders, said first-base-register means, said first-carry register-means, said second-base-register means, said second-register means, said base-accumulator means, and said carry-accumulator means, for switching said plurality of full adders for simultaneously adding the base bits and carry bits of the first sum in said base-accumulator means and said carry accumulator means to the carry bits of the second integer B to generate the third integer C, and storing the base bits and carry bits of the third integer C in said base-accumulator means and said carry accumulator means, respectively.

Claim 18

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, wherein the first integer A is represented by the binary numbers {A[i]} in the form A = A[n-1]2 n-1 + A[n-2]2 n-2 + A[n-3]2 n-3 + ... + A[1]2 + A[0], the second integer B is represented by the binary numbers {B[i]} in the form B = B[n-1]2 n-1 + B[n-2]2 n-2 + B[n-3]2 n-3 + ... + B[1]2 + B[0], the third integer C is represented by the binary numbers {C[i]} in the form C = C[n-1]2 n-1 + C[n-2]2 n-2 + C[n-3]2 n-3 + ... + C[1]2 + C[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p = P[n-1]2 n-1 + P[n-2]2 n-2 + P[n-3]2 n-3 + ... + P[1]2 + P[0], whereby C = A·B mod p, comprising: first register means for storing the first integer A; second register means for storing the second integer B; feedback means for generating a feedback number F, wherein the feedback number F is the two's compliment 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 B shifted left from said second register means for adding the feedback number F to the second integer B, thereby partially reducing the second integer B; arithmetic means coupled to said first register means, and said second register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for adding the second integer B to the third integer C; accumulator means coupled to said arithmetic means for storing the third integer C; 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 A by the second integer B, for 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 C in said accumulator means; and means coupled to said accumulator means and responsive to the third integer C being greater than the fourth integer p, for reducing third integer C modulo the fourth integer p.

Claim 19

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, wherein the first integer A is represented by the binary numbers {A[i]} in the form A = A[n-1]2 n-1 + A[n-2]2 n-2 + A[n-3]2 n-3 + ... + A[1]2 + A[0], the second integer B is represented by the binary numbers {B[i]} in the form B = B[n-1]2 n-1 + B[n-2]2 n-2 + B[n-3]2 n-3 + ... + B[1]2 + B[0], the third integer C is represented by the binary numbers {C[i]} in the form C = C[n-1]2 n-1 + C[n-2]2 n-2 + C[n-3]2 n-3 + ... + C[1]2 + C[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p = P[n-1]2 n-1 + P[n-2]2 n-2 + P[n-3]2 n-3 + ... + P[1]2 + P[0], whereby C = A·B mod p, comprising: first register means for storing the first integer A; second register means for storing the second integer B; feedback means for generating a feedback number F, wherein the feedback number F is the two's compliment 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 B shifted left from said second register means for adding the feedback number F to the second integer B, thereby partially reducing the second integer B; arithmetic means coupled to said first register means, and said second register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for adding the second integer B to the third integer C; accumulator means coupled to said arithmetic means for storing the third integer C; 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 A by the second integer B, for 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 C in said accumulator means; and means coupled to said accumulator means and responsive to the third integer C being greater than the fourth integer p, for reducing third integer C modulo the fourth integer p.

Claim 20

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, wherein the first integer A is represented by the binary numbers {A[i]} in the form A = A[n-1]2 n-1 + A[n-2]2 n-2 + A[n-3]2 n-3 + ... + A[1]2 + A[0], second integer B is represented by the binary numbers {B[i]} in the form B = B[n-1]2 n-1 + B[n-2]2 n-2 + B[n-3]2 n-3 + ... + B[1]2 + B[0], the third integer C is represented by the binary numbers {C[i]} in the form C = C[n-1]2 n-1 + C[n-2]2 n-2 + C[n-3]2 n-3 + ... + C[1]2 + C[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p = P[n-1]2 n-1 + P[n-2]2 n-2 + P[n-3]2 n-3 + ... + P[1]2 + P[0], whereby C = A·B mod p, comprising: first register means for storing the first integer A; second register means for storing the second integer B; 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; arithmetic means coupled to said first register means and said second register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for adding the second integer B to the third integer C; accumulator means coupled to said arithmetic means for storing the third integer C; 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 A by the second integer B, for 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 C in said accumulator means; and means coupled to said accumulator means and responsive to the third integer C being greater than fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 21

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, wherein the first integer A is represented by the binary numbers {A[i]} in the form A = A[n-1]2 n-1 + A[n-2]2 n-2 + A[n-3]2 n-3 + ... + A[1]2 + A[0], second integer B is represented by the binary numbers {B[i]} in the form B = B[n-1]2 n-1 + B[n-2]2 n-2 + B[n-3]2 n-3 + ... + B[1]2 + B[0], the third integer C is represented by the binary numbers {C[i]} in the form C = C[n-1]2 n-1 + C[n-2]2 n-2 + C[n-3]2 n-3 + ... + C[1]2 + C[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p = P[n-1]2 n-1 + P[n-2]2 n-2 + P[n-3]2 n-3 + ... + P[1]2 + P[0], whereby C = A·B mod p, comprising: first register means for storing the first integer A; second register means for storing the second integer B; 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; arithmetic means coupled to said first register means and said second register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for adding the second integer B to the third integer C; accumulator means coupled to said arithmetic means for storing the third integer C; 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 A by the second integer B, for 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 C in said accumulator means; and means coupled to said accumulator means and responsive to the third integer C being greater than fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 22

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, wherein the first integer A is represented by the binary numbers {A[i]} in the form A = A[n-1]2 n-1 + A[n-2]2 n-2 + A[n-3]2 n-3 + ... + A[1]2 + A[0], second integer B is represented by the binary numbers {B[i]} in the form B = B[n-1]2 n-1 + B[n-2]2 n-2 + B[n-3]2 n-3 + ... + B[1]2 + B[0], the third integer C is represented by the binary numbers {C[i]} in the form C = C[n-1]2 n-1 + C[n-2]2 n-2 + C[n-3]2 n-3 + ... + C[1]2 + C[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p = P[n-1]2 n-1 + P[n-2]2 n-2 + P[n-3]2 n-3 + ... + P[1]2 + P[0], whereby C = A·B mod p, comprising: first-register means for storing the first integer A; second-register means for storing the second integer B; feedback means for generating and storing a feedback number F, wherein the feedback number F is the two's compliment of the fourth integer p and thereby F = 2 n - p; first-partial-reduction means coupled to said second register means and responsive to in the most significant position of the second integer B shifted left from said second register means, for adding the feedback number F to the second integer B, thereby partially reducing the second integer B; arithmetic means coupled to said first register means, and said second register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for adding the second integer B to the third integer C; accumulator means coupled to said arithmetic means for storing the third integer C; and means coupled to said accumulator means and responsive to the third integer C being greater than fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 23

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, wherein the first integer A is represented by the binary numbers {A[i]} in the form A = A[n-1]2 n-1 + A[n-2]2 n-2 + A[n-3]2 n-3 + ... + A[1]2 + A[0], second integer B is represented by the binary numbers {B[i]} in the form B = B[n-1]2 n-1 + B[n-2]2 n-2 + B[n-3]2 n-3 + ... + B[1]2 + B[0], the third integer C is represented by the binary numbers {C[i]} in the form C = C[n-1]2 n-1 + C[n-2]2 n-2 + C[n-3]2 n-3 + ... + C[1]2 + C[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p = P[n-1]2 n-1 + P[n-2]2 n-2 + P[n-3]2 n-3 + ... + P[1]2 + P[0], whereby C = A·B mod p, comprising: first-register means for storing the first integer A; second-register means for storing the second integer B; feedback means for generating and storing a feedback number F, wherein the feedback number F is the two's compliment of the fourth integer p and thereby F = 2 n - p; first-partial-reduction means coupled to said second register means and responsive to in the most significant position of the second integer B shifted left from said second register means, for adding the feedback number F to the second integer B, thereby partially reducing the second integer B; arithmetic means coupled to said first register means, and said second register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for adding the second integer B to the third integer C; accumulator means coupled to said arithmetic means for storing the third integer C; and means coupled to said accumulator means and responsive to the third integer C being greater than fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 24

A modulo arithmetic processor chip according to claim 14 or claim 15 wherein said arithmetic means includes a plurality of full adders coupled to said second register means, for simultaneously adding the second integer B to the third integer C.

Claim 25

A modulo arithmetic processor chip according to claim 14 or claim 15 wherein said arithmetic means includes a plurality of half adders coupled to said second register means, for simultaneously adding the second integer B to the third integer C.

Claim 26

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, and wherein the base bits of the first integer A are represented by the binary numbers {A₁[i]} in the form A₁ = A₁[n-1]2 n-1 + A₁[n-2]2 n-2 + A₁[n-3]2 n-3 + ... + A₁[1]2 + A₁[0], the carry bits of the first integer A are represented by the binary numbers {A₂[i]} in the form A₂ = A₂[n-1]2 n-1 + A₂[n-2]2 n-2 + A₂[n-3]2 n-3 + ... + A₂[1]2 + A₂[0], the base bits of the second integer B are represented by the binary number {B₁[i]} in the form B₁ = B₁[n-1]2 n-1 + B₁[n-2]2 n-2 + B₁[n-3]2 n-3 + ... + B₁[1]2 + B₁[0], the carry bits of the second integer B are represented by the binary numbers {B₂[i]} in the form B₂ = B₂[n-1]2 n-1 + B₂[n-2]2 n-2 + B₂[n-3]2 n-3 + ... + B₂[1]2 + B₂[0], the base bits of the third integer C are represented by the binary numbers {C₁[i]} in the form C₁ = C₁[n-1]2 n-1 + C₁[n-2]2 n-2 + C₁[n-3]2 n-3 + ... + C₁[n-2]2 + C₁[0], the carry bits of the third integer C are represented by the binary numbers {C₂[i]} in the form C₂ = C₂[n-1]2 n-1 + C₂[n-2]2 n-2 + C₂[n-3]2 n-3 + ... + C₂[n-2]2 + C₂[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p= P[n-1]2 n-1 + P[n-2]2 n-2 + P[n-3]2 n-3 + ... + P[1]2 + P[0], whereby C = A·B mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base bits of the second integer B; second-carry-register means for storing the carry bits of the second integer B; feedback means for generating a first feedback number F₁, a second feedback number F₂, a third feedback number F₃, and a fourth feedback number F₄, wherein the first feedback number F₁ is the two's complement of fourth integer p and thereby F₁ = 2 n - p, the second feedback number F₂ equals two times first feedback number F₁ and thereby F₂ = 2F₁ mod p, the third feedback number F₃ equals three times first feedback number F₁ and thereby F₃ = 3F₁ mod p, the fourth feedback number F₄ equals four times first feedback number F₁ and thereby F₄ = 4F₁ mod p; first-partial-reduction means coupled to said second-base-register means, to said second-carry-register means and to said feedback means and responsive to the most significant base bits and carry bits of the second integer B shifted left from said second-base-register means and said second-carry-register means, for adding first, second, third or fourth feedback number according to a preselected choice of the shifted-left base bits and carry bits of the second integer B, to the second integer B, thereby partially reducing the second integer B; arithmetic means having a plurality of full adders, coupled to said first-baee-register means, said first-carry-register means, said second-base-register means, and said second-carry-register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for simultaneously adding with said plurality of full adders the base bits and carry bits of the second integer B to the respective base bits of the third integer C to generate a first sum having base bits and carry bits, and subsequently adding with said plurality of full adders the base bits and carry bits of the first sum to the respective carry bits of the third integer C; accumulator-base means coupled to said arithmetic means for storing the base bits of the third integer C; accumulator-carry means coupled to said arithmetic means for storing the carry bits of the third integer C; overflow means coupled to said accumulator means for storing an overflow integer I; second-partial-reduction means coupled to said overflow means, said feedback means, said first-base-register means and said second-base-register means, and responsive to the overflow integer I = 1, 2, 3, or 4, respectively, for fetching the first, second, third, or fourth feedback number, respectively, from said feedback means into said second-base-register means and adding the first, second, third, or fourth feedback number, respectively, using arithmetic means to the third integer C in said accumulator-base means and said accumulator-carry means; and means coupled to said accumulator-base-means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 27

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, and wherein the base bits of the first integer A are represented by the binary numbers {A₁[i]} in the form A₁ = A₁[n-1]2 n-1 + A₁[n-2]2 n-2 + A₁[n-3]2 n-3 + ... + A₁[1]2 + A₁[0], the carry bits of the first integer A are represented by the binary numbers {A₂[i]} in the form A₂ = A₂[n-1]2 n-1 + A₂[n-2]2 n-2 + A₂[n-3]2 n-3 + ... + A₂[1]2 + A₂[0], the base bits of the second integer B are represented by the binary number {B₁[i]} in the form B₁ = B₁[n-1]2 n-1 + B₁[n-2]2 n-2 + B₁[n-3]2 n-3 + ... + B₁[1]2 + B₁[0], the carry bits of the second integer B are represented by the binary numbers {B₂[i]} in the form B₂ = B₂[n-1]2 n-1 + B₂[n-2]2 n-2 + B₂[n-3]2 n-3 + ... + B₂[1]2 + B₂[0], the base bits of the third integer C are represented by the binary numbers {C₁[i]} in the form C₁ = C₁[n-1]2 n-1 + C₁[n-2]2 n-2 + C₁[n-3]2 n-3 + ... + C₁[n-2]2 + C₁[0], the carry bits of the third integer C are represented by the binary numbers {C₂[i]} in the form C₂ = C₂[n-1]2 n-1 + C₂[n-2]2 n-2 + C₂[n-3]2 n-3 + ... + C₂[n-2]2 + C₂[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p= P[n-1]2 n-1 + P[n-2]2 n-2 + P[n-3]2 n-3 + ... + P[1]2 + P[0], whereby C = A·B mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base bits of the second integer B; second-carry-register means for storing the carry bits of the second integer B; feedback means for generating a first feedback number F₁, a second feedback number F₂, a third feedback number F₃, and a fourth feedback number F₄, wherein the first feedback number F₁ is the two's complement of fourth integer p and thereby F₁ = 2 n - p, the second feedback number F₂ equals two times first feedback number F₁ and thereby F₂ = 2F₁ mod p, the third feedback number F₃ equals three times first feedback number F₁ and thereby F₃ = 3F₁ mod p, the fourth feedback number F₄ equals four times first feedback number F₁ and thereby F₄ = 4F₁ mod p; first-partial-reduction means coupled to said second-base-register means, to said second-carry-register means and to said feedback means and responsive to the most significant base bits and carry bits of the second integer B shifted left from said second-base-register means and said second-carry-register means, for adding first, second, third or fourth feedback number according to a preselected choice of the shifted-left base bits and carry bits of the second integer B, to the second integer B, thereby partially reducing the second integer B; arithmetic means having a plurality of full adders, coupled to said first-baee-register means, said first-carry-register means, said second-base-register means, and said second-carry-register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for simultaneously adding with said plurality of full adders the base bits and carry bits of the second integer B to the respective base bits of the third integer C to generate a first sum having base bits and carry bits, and subsequently adding with said plurality of full adders the base bits and carry bits of the first sum to the respective carry bits of the third integer C; accumulator-base means coupled to said arithmetic means for storing the base bits of the third integer C; accumulator-carry means coupled to said arithmetic means for storing the carry bits of the third integer C; overflow means coupled to said accumulator means for storing an overflow integer I; second-partial-reduction means coupled to said overflow means, said feedback means, said first-base-register means and said second-base-register means, and responsive to the overflow integer I = 1, 2, 3, or 4, respectively, for fetching the first, second, third, or fourth feedback number, respectively, from said feedback means into said second-base-register means and adding the first, second, third, or fourth feedback number, respectively, using arithmetic means to the third integer C in said accumulator-base means and said accumulator-carry means; and means coupled to said accumulator-base-means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 28

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, whereby C = A·B mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base bits of the second integer B; second-carry-register means for storing the carry bits of the second integer B; feedback means for generating a first feedback number F₁, a second feedback number F₂, a third feedback number F₃, and a fourth feedback number F₄, wherein the first feedback number F₁ is the two's complement of fourth integer p and thereby F₁ = 2 n - p, the second feedback number F₂ equals two times first feedback number F₁ and thereby F₂ = 2F₁ mod p, the third feedback number F₃ equals three times first feedback number F₁ and thereby F₃ = 3F₁ mod p, the fourth feedback number F₄ equals four times first feedback number F₁ and thereby F₄ = 4F₁ mod p; arithmetic means coupled to said first-base-register means, said first-carry-register means, said second-base-register means, and said second-carry-register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for adding the base bits and carry bits of the second integer B to the respective base bits of the third integer C to generate a first sum having base bits and carry bits, and subsequently adding the base bits and carry bits of the first sum to the respective carry bits of the third integer C; accumulator-base means coupled to said arithmetic means for storing the base bits of the third integer C; accumulator-carry means coupled to said arithmetic means for storing the carry bits of the third integer C; overflow means coupled to said accumulator means for storing an overflow integer I; second-partial-reduction means coupled to said overflow means, said feedback means, said first-base-register means and said second-base-register means, and responsive to the overflow integer I = 1, 2, 3, or 4, for fetching the first, second, third, or fourth feedback number, respectively, from said feedback means into said second-base-register means and adding the first, second, third, or fourth feedback number, respectively, using arithmetic means to the third integer C in said accumulator-base means and said accumulator-carry means; and means coupled to said accumulator-base means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 29

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, whereby C = A·B mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base bits of the second integer B; second-carry-register means for storing the carry bits of the second integer B; feedback means for generating a first feedback number F₁, a second feedback number F₂, a third feedback number F₃, and a fourth feedback number F₄, wherein the first feedback number F₁ is the two's complement of fourth integer p and thereby F₁ = 2 n - p, the second feedback number F₂ equals two times first feedback number F₁ and thereby F₂ = 2F₁ mod p, the third feedback number F₃ equals three times first feedback number F₁ and thereby F₃ = 3F₁ mod p, the fourth feedback number F₄ equals four times first feedback number F₁ and thereby F₄ = 4F₁ mod p; arithmetic means coupled to said first-base-register means, said first-carry-register means, said second-base-register means, and said second-carry-register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for adding the base bits and carry bits of the second integer B to the respective base bits of the third integer C to generate a first sum having base bits and carry bits, and subsequently adding the base bits and carry bits of the first sum to the respective carry bits of the third integer C; accumulator-base means coupled to said arithmetic means for storing the base bits of the third integer C; accumulator-carry means coupled to said arithmetic means for storing the carry bits of the third integer C; overflow means coupled to said accumulator means for storing an overflow integer I; second-partial-reduction means coupled to said overflow means, said feedback means, said first-base-register means and said second-base-register means, and responsive to the overflow integer I = 1, 2, 3, or 4, for fetching the first, second, third, or fourth feedback number, respectively, from said feedback means into said second-base-register means and adding the first, second, third, or fourth feedback number, respectively, using arithmetic means to the third integer C in said accumulator-base means and said accumulator-carry means; and means coupled to said accumulator-base means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 30

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, whereby C = A·B mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base bits of the second integer B; second-carry-register means for storing the carry bits of the second integer B; feedback means for generating a first feedback number F₁, a second feedback number F₂, a third feedback number F₃, and a fourth feedback number F₄, wherein the first feedback number F₁ is the two's complement of fourth integer p and thereby F₁ = 2 n - p, the second feedback number F₂ equals two times first feedback number F₁ and thereby F₂ = 2F₁ mod p, the third feedback number F₃ equals three times first feedback number F₁ and thereby F₃ = 3F₁ mod p, the fourth feedback number F₄ equals four times first feedback number F₁ and thereby F₄ = 4F₁ mod p; first-partial-reduction means coupled to said second-base-register means, to said second-carry-register means and to said feedback means and responsive to the most significant base bits and carry bits of the second integer B shifted left from said second-base-register means and said second-carry-register means for adding first, second, third or fourth feedback number according to a preselected choice of the shifted-left base bits and carry bits of the second integer B, to the second integer B, thereby partially reducing the second integer B; arithmetic means coupled to said first-base-register means, said first-carry-register means, said second-base-register means, and said second-carry-register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for adding the base bits and carry bits of the second integer B to the respective base bits of the third integer C to generate a first sum having base bits and carry bits, and subsequently adding the base bits and carry bits of the first sum to the respective carry bits of the third integer C; accumulator-base means coupled to said accumulator means for storing the base bits of the third integer C; accumulator-carry means coupled to said accumulator means for storing the carry bits of the third integer C; overflow means coupled to said accumulator means for storing an overflow integer I; means coupled to said accumulator-base means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 31

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, whereby C = A·B mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base bits of the second integer B; second-carry-register means for storing the carry bits of the second integer B; feedback means for generating a first feedback number F₁, a second feedback number F₂, a third feedback number F₃, and a fourth feedback number F₄, wherein the first feedback number F₁ is the two's complement of fourth integer p and thereby F₁ = 2 n - p, the second feedback number F₂ equals two times first feedback number F₁ and thereby F₂ = 2F₁ mod p, the third feedback number F₃ equals three times first feedback number F₁ and thereby F₃ = 3F₁ mod p, the fourth feedback number F₄ equals four times first feedback number F₁ and thereby F₄ = 4F₁ mod p; first-partial-reduction means coupled to said second-base-register means, to said second-carry-register means and to said feedback means and responsive to the most significant base bits and carry bits of the second integer B shifted left from said second-base-register means and said second-carry-register means for adding first, second, third or fourth feedback number according to a preselected choice of the shifted-left base bits and carry bits of the second integer B, to the second integer B, thereby partially reducing the second integer B; arithmetic means coupled to said first-base-register means, said first-carry-register means, said second-base-register means, and said second-carry-register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for adding the base bits and carry bits of the second integer B to the respective base bits of the third integer C to generate a first sum having base bits and carry bits, and subsequently adding the base bits and carry bits of the first sum to the respective carry bits of the third integer C; accumulator-base means coupled to said accumulator means for storing the base bits of the third integer C; accumulator-carry means coupled to said accumulator means for storing the carry bits of the third integer C; overflow means coupled to said accumulator means for storing an overflow integer I; means coupled to said accumulator-base means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 32

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, whereby C = A·B mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base bits of the second integer B; second-carry-register means for storing the carry bits of the second integer B; feedback means for generating a first feedback number F₁, wherein the first feedback number F₁ is the two's complement of fourth integer p and thereby F₁ = 2 n - p; arithmetic means coupled to said first-base-register means, said first-carry-register means, said second-base-register means and said second-carry-register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for adding the base bits and carry bits of the second integer B to the respective base bits of the third integer C to generate a first sum having base bits and carry bits, and subsequently adding the base bits and carry bits of the first sum to the respective carry bits of the third integer C; accumulator-base means coupled to said arithmetic means for storing the base bits of the third integer C; accumulator-carry means coupled to said arithmetic means for storing the carry bits of the third integer C; overflow means coupled to said accumulator means for storing an overflow integer I; and means responsive coupled to said accumulator-base means to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 33

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, whereby C = A·B mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base bits of the second integer B; second-carry-register means for storing the carry bits of the second integer B; feedback means for generating a first feedback number F₁, wherein the first feedback number F₁ is the two's complement of fourth integer p and thereby F₁ = 2 n - p; arithmetic means coupled to said first-base-register means, said first-carry-register means, said second-base-register means and said second-carry-register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for adding the base bits and carry bits of the second integer B to the respective base bits of the third integer C to generate a first sum having base bits and carry bits, and subsequently adding the base bits and carry bits of the first sum to the respective carry bits of the third integer C; accumulator-base means coupled to said arithmetic means for storing the base bits of the third integer C; accumulator-carry means coupled to said arithmetic means for storing the carry bits of the third integer C; overflow means coupled to said accumulator means for storing an overflow integer I; and means responsive coupled to said accumulator-base means to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 34

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, and wherein the base bits of the first integer A are represented by the binary numbers {A₁[i]} in the form A₁ = A₁[n-1]2 n-1 + A₁[n-2]2 n-2 + A₁[n-3]2 n-3 + ... + A₁[1]2 + A₁[0], the carry bits of the first integer A are represented by the binary numbers {A₂[i]} in the form A₂ = A₂[n-1]2 n-1 + A₂[n-2]2 n-2 + A₂[n-3]2 n-3 + ... + A₂[1]2 + A₂[0], the base bits of the second integer B are represented by the binary numbers {B₁[i]} in the form B₁ = B₁[n-1]2 n-1 + B₁[n-2]2 n-2 + B₁[n-3]2 n-3 + ... + B₁[1]2 + B₁[0], the carry bits of the second integer B are represented by the binary numbers {B₂[i]} in the form B₂ = B₂[n-1]2 n-1 + B₂[n-2]2 n-2 + B₂[n-3]2 n-3 + ... + B₂[1]2 + B₂[0], the base bits of the third integer C are represented by the binary numbers {C₁[i]} in the form C₁ = C₁[n-1]2 n-1 + C₁[n-2]2 n-2 + C₁[n-3]2 n-3 + ... + C₁[n-2]2 + C₁[0], the carry bits of the third integer C are represented by the binary numbers {C₂[i]} in the form C₂ = C₂[n-1]2 n-1 + C₂[n-2]2 n-2 + C₂[n-3]2 n-3 + ... + C₂[n-2]2 + C₂[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p = P[n-1]2 n-1 + P[n-2]2 n-2 + P[n-3]2 n-3 + ... + P[1]2 + P[0], whereby C = A·B mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base units of the second integer B; second-carry-register means for storing the carry bits of the second integer B; feedback means for generating a first feedback number F₁, a second feedback number F₂, a third feedback number F₃, and a fourth feedback number F₄, wherein the first feedback number F₁ is the two's complement of fourth integer p and thereby F₁ = 2 n - p, the second feedback number F₂ equals two times first feedback number F₁ and thereby F₂ = 2F₁ mod p, the third feedback number F₃ equals three times first feedback number F₁ and thereby F₃ = 3F₁ mod p, the fourth feedback number F₄ equals four times first feedback number F₁ and thereby F₄ = 4F₁ mod p; first-partial-reduction means coupled to said second-base-register means, to said second-carry-register means and to said feedback means and responsive to the most significant base bits and carry bits of the second integer B shifted left from said second-base-register means and said second-carry-register means, for adding first, second, third or fourth feedback number according to a preselected choice of the shifted-left base bits and carry bits of the second integer B, to the second integer B, thereby partially reducing the second integer B; arithmetic means having a plurality of full adders, coupled to said first-base-register means, said first-carry-register means, said second-base-register means, and said second-carry-register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for simultaneously adding with said plurality of full adders the base bits and carry bits of the second integer B to the respective base bits of the third integer C to generate a first sum having base bits and carry bits, and subsequently adding with said plurality of full adders the base bits and carry bits of the first sum to the respective carry bits of the third integer C; accumulator-base means coupled to said arithmetic means for storing the base bits of the third integer C; accumulator-carry means coupled to said arithmetic means for storing the carry bits of the third integer C; overflow means coupled to said accumulator means for storing an overflow integer I; second-partial-reduction means coupled to said overflow means, said feedback means, said first-base-register means and said second-base-register means, and responsive to the completion of multiplying the first integer A by the second integer B, for transferring the overflow integer I into said first register means, transferring the first feedback number F₁ into said second register means, and multiplying the first feedback number F₁ by the overflow integer I to generate a product, and adding the product to the third integer C in said accumulator-base means and said accumulator-carry means; and means coupled to said accumulator-base-means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 35

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, and wherein the base bits of the first integer A are represented by the binary numbers {A₁[i]} in the form A₁ = A₁[n-1]2 n-1 + A₁[n-2]2 n-2 + A₁[n-3]2 n-3 + ... + A₁[1]2 + A₁[0], the carry bits of the first integer A are represented by the binary numbers {A₂[i]} in the form A₂ = A₂[n-1]2 n-1 + A₂[n-2]2 n-2 + A₂[n-3]2 n-3 + ... + A₂[1]2 + A₂[0], the base bits of the second integer B are represented by the binary numbers {B₁[i]} in the form B₁ = B₁[n-1]2 n-1 + B₁[n-2]2 n-2 + B₁[n-3]2 n-3 + ... + B₁[1]2 + B₁[0], the carry bits of the second integer B are represented by the binary numbers {B₂[i]} in the form B₂ = B₂[n-1]2 n-1 + B₂[n-2]2 n-2 + B₂[n-3]2 n-3 + ... + B₂[1]2 + B₂[0], the base bits of the third integer C are represented by the binary numbers {C₁[i]} in the form C₁ = C₁[n-1]2 n-1 + C₁[n-2]2 n-2 + C₁[n-3]2 n-3 + ... + C₁[n-2]2 + C₁[0], the carry bits of the third integer C are represented by the binary numbers {C₂[i]} in the form C₂ = C₂[n-1]2 n-1 + C₂[n-2]2 n-2 + C₂[n-3]2 n-3 + ... + C₂[n-2]2 + C₂[0], and the fourth integer p is represented by the binary numbers {P[i]} in the form p = P[n-1]2 n-1 + P[n-2]2 n-2 + P[n-3]2 n-3 + ... + P[1]2 + P[0], whereby C = A·B mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base units of the second integer B; second-carry-register means for storing the carry bits of the second integer B; feedback means for generating a first feedback number F₁, a second feedback number F₂, a third feedback number F₃, and a fourth feedback number F₄, wherein the first feedback number F₁ is the two's complement of fourth integer p and thereby F₁ = 2 n - p, the second feedback number F₂ equals two times first feedback number F₁ and thereby F₂ = 2F₁ mod p, the third feedback number F₃ equals three times first feedback number F₁ and thereby F₃ = 3F₁ mod p, the fourth feedback number F₄ equals four times first feedback number F₁ and thereby F₄ = 4F₁ mod p; first-partial-reduction means coupled to said second-base-register means, to said second-carry-register means and to said feedback means and responsive to the most significant base bits and carry bits of the second integer B shifted left from said second-base-register means and said second-carry-register means, for adding first, second, third or fourth feedback number according to a preselected choice of the shifted-left base bits and carry bits of the second integer B, to the second integer B, thereby partially reducing the second integer B; arithmetic means having a plurality of full adders, coupled to said first-base-register means, said first-carry-register means, said second-base-register means, and said second-carry-register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for simultaneously adding with said plurality of full adders the base bits and carry bits of the second integer B to the respective base bits of the third integer C to generate a first sum having base bits and carry bits, and subsequently adding with said plurality of full adders the base bits and carry bits of the first sum to the respective carry bits of the third integer C; accumulator-base means coupled to said arithmetic means for storing the base bits of the third integer C; accumulator-carry means coupled to said arithmetic means for storing the carry bits of the third integer C; overflow means coupled to said accumulator means for storing an overflow integer I; second-partial-reduction means coupled to said overflow means, said feedback means, said first-base-register means and said second-base-register means, and responsive to the completion of multiplying the first integer A by the second integer B, for transferring the overflow integer I into said first register means, transferring the first feedback number F₁ into said second register means, and multiplying the first feedback number F₁ by the overflow integer I to generate a product, and adding the product to the third integer C in said accumulator-base means and said accumulator-carry means; and means coupled to said accumulator-base-means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 36

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, whereby C = A·B mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base bits of the second integer B; second-carry-register means for storing the carry bits of the second integer B; feedback means for generating a first feedback number F₁, a second feedback number F₂, a third feedback number F₃, and a fourth feedback number F₄, wherein the first feedback number F₁ is the two's complement of fourth integer p and thereby F₁ = 2 n - p, the second feedback number F₂ equals two times first feedback number F₁ and thereby F₂ = 2F₁ mod p, the third feedback number F₃ equals three times first feedback number F₁ and thereby F₃ = 3F₁ mod p, the fourth feedback number F₄ equals four times first feedback number F₁ and thereby F₄ = 4F₁ mod p; arithmetic means coupled to said first-base-register means, said first-carry-register means, said second-base-register means, and said second-carry-register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for adding the base bits and carry bits of the second integer B to the respective base bits of the third integer C to generate a first sum having base bits and carry bits, and subsequently adding the base bits and carry bits of the first sum to the respective carry bits of the third integer C; accumulator-base means coupled to said arithmetic means for storing the base bits of the third integer C; accumulator-carry means coupled to said arithmetic means for storing the carry bits of the third integer C; overflow means coupled to said accumulator means for storing an overflow integer I; second-partial-reduction means coupled to said overflow means, said feedback means, said first-base-register means and said second-base-register means, and responsive to the completion of multiplying the first integer A by the second integer B, for transferring the overflow integer I into said first register means, transferring the first feedback number F₁ into said second register means, and multiplying the first feedback number F₁ by the overflow integer I to generate a product, and adding the product to the third integer C in said accumulator-base means and said accumulator-carry means; and means coupled to said accumulator-base means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 37

A modulo arithmetic processor chip for multiplying a first integer A having n-bits by a second integer B having n-bits, wherein the first integer A times the second integer B equals a third integer C having n-bits, modulo a fourth integer p having n-bits, whereby C = A·B mod p, comprising: first-base-register means for storing the base bits of the first integer A; first-carry-register means for storing the carry bits of the first integer A; second-base-register means for storing the base bits of the second integer B; second-carry-register means for storing the carry bits of the second integer B; feedback means for generating a first feedback number F₁, a second feedback number F₂, a third feedback number F₃, and a fourth feedback number F₄, wherein the first feedback number F₁ is the two's complement of fourth integer p and thereby F₁ = 2 n - p, the second feedback number F₂ equals two times first feedback number F₁ and thereby F₂ = 2F₁ mod p, the third feedback number F₃ equals three times first feedback number F₁ and thereby F₃ = 3F₁ mod p, the fourth feedback number F₄ equals four times first feedback number F₁ and thereby F₄ = 4F₁ mod p; arithmetic means coupled to said first-base-register means, said first-carry-register means, said second-base-register means, and said second-carry-register means, and responsive to the least significant position of the first integer A shifted right from said first register means, for adding the base bits and carry bits of the second integer B to the respective base bits of the third integer C to generate a first sum having base bits and carry bits, and subsequently adding the base bits and carry bits of the first sum to the respective carry bits of the third integer C; accumulator-base means coupled to said arithmetic means for storing the base bits of the third integer C; accumulator-carry means coupled to said arithmetic means for storing the carry bits of the third integer C; overflow means coupled to said accumulator means for storing an overflow integer I; second-partial-reduction means coupled to said overflow means, said feedback means, said first-base-register means and said second-base-register means, and responsive to the completion of multiplying the first integer A by the second integer B, for transferring the overflow integer I into said first register means, transferring the first feedback number F₁ into said second register means, and multiplying the first feedback number F₁ by the overflow integer I to generate a product, and adding the product to the third integer C in said accumulator-base means and said accumulator-carry means; and means coupled to said accumulator-base means and responsive to the third integer C being greater than the fourth integer p, for reducing the third integer C modulo the fourth integer p.

Claim 38

A modulo arithmetic processor chip according to any one of claims 19 to 21 and 23, wherein said arithmetic means includes a plurality of full adders coupled to said second-base-register means and said second-carry-register means, for simultaneously adding the base bits and carry bits of the second integer B to the base bits of the third integer C to generate the first sum having base bits and carry bits.

Claim 39

The modulo arithmetic processor chip as set forth in claim 24 further including multiplexer means for controlling said plurality of full adders to add the base bits and carry bits of the first sum to the carry bits of the third integer C.--