Efficient modular reduction and modular multiplication

A circuit for producing A mod N, where A is a binary number considered as having n blocks with k bits each and where N is a binary number considered as having m blocks of k bits each, said circuit comprising:

• a shift register with mk+2k bits arranged in k bit blocks for initially holding the m highest order blocks of A and for receiving subsequent k bit blocks of A shifted into the lowest order k bit block of said shift register;
• a storage register for holding mk bits representing the value Rm+1 mod N, where R=2k;
• a multiplier circuit for multiplying the contents of said storage register by the k bits in the highest order position in said shift register;
• a first adder circuit for adding the output from said multiplier to the low order mk+k bits in said shift register;
• and
• a second adder for adding the contents of said storage register to the output from said first adder upon the condition that said first adder circuit produces a carry out signal, otherwise adding zero.

A method for producing A×B mod N where A and B are binary numbers with at least one of them being considered as having m blocks with k bits each and where N is a binary number, said method comprising the steps of:

• loading a value Rm+1 mod N, where R=2k, into a first register;
• loading A into a multiplicand register;
• setting an intermediate result register to zero;
• for values of i ranging from m−1 to 1 carrying out steps (a) through (g) below:
• (a) forming a first product of A and Bi where Bi is the ith k bit block of B with B0 being the low order block;
• (b) adding, in a first unconditional addition, the contents of said intermediate result register to said first product;
• (c) upon the condition that said first addition produces a carry out, adding, in a first conditional addition, the contents of said first register to the results of said first unconditional addition to produce an output having k high order bits and mk low order bits, otherwise adding zero to produce said output;
• (d) forming a second product of the contents of said first register and the k high order bits from the output of said first conditional addition;
• (e) adding, in a second unconditional addition, the mk low order bits from said first conditional addition with k bits, which are zero, appended on the rightmost end of said mk low order bits, and said second product;
• (f) upon condition that said second unconditional addition produces a carry out, adding, in a second conditional addition, the contents of said first register to the results of said second unconditional addition, otherwise adding zero;
• and
• (g) loading the result of said second unconditional addition operation to said intermediate result register.

A circuit for producing A×B mod N, where A and B are binary numbers with at least one of them being considered as having m blocks with k bits each and where N is a binary number, said circuit comprising:

• an intermediate storage register;
• a multiplicand register for storing the value of A;
• a constant register for storing the value Rm+1 mod N where R=2k;
• a first multiplier for producing the product of A and Bi where Bi is the ith k bit block of B with B0 being the low order block;
• a first unconditioned adder for producing the sum of the product from said first multiplier and the contents of said intermediate storage register, said first unconditioned adder also producing a first carry signal;
• a first conditioned adder for producing the sum of the contents of said constant register and the sum from said first unconditioned adder upon the condition that said first carry signal indicates a carry out of the leftmost bit position from said first unconditioned adder;
• a second multiplier for producing the product of the contents of said constant register and the leftmost k bits in said sum produced by said first conditioned adder;
• a second unconditioned adder for producing the sum of the product from said second multiplier and the rightmost mk bits from first conditioned adder with k bits, which are zero, appended on the rightmost end of said rightmost mk bits, said second unconditioned adder also producing a second carry signal;
• a second conditioned adder for producing the sum of the contents of said constant register and the sum from said second unconditioned adder upon the condition that said second carry signal indicates a carry out of the leftmost bit position from said second unconditioned adder;
• and
• a feedback connection for supplying the sum from said second conditioned adder to said intermediate storage register.

A method for producing A×B mod N where A and B are binary numbers with at least one of them being considered as having m blocks with k bits each and where N is a binary number, said method comprising the steps of:

• loading a value Rm+1 mod N, where R=2k, into a first register;
• loading A into a multiplicand register;
• setting an intermediate result register to zero;
• for values of i ranging from m−1 to 0 carrying out steps (a) through (g) below:
• (a) forming a first product of the contents of said first register and the leftmost k bits in said intermediate result register;
• (b) adding, in a first unconditioned addition, said first product and the low order mk bits from said intermediate result register with k bits, which are zero, appended on the rightmost end of said mk bits and;
• (c) upon condition that said first unconditioned addition produces a carry out, adding, in a first conditioned addition, the output from said first unconditioned addition and the contents of said first register, otherwise adding zero;
• (d) forming a second product of the contents of said multiplicand register and Bi where Bi is the ith k bit block of B with B0 being the low order block;
• (e) adding, in a second unconditioned addition, said second product and the output from said first conditioned addition;
• (f) upon condition that said second unconditioned addition produces a carry out, adding, in a second conditioned addition, the output from said second unconditioned addition and the contents of said first register, otherwise adding zero;
• and
• (g) loading the result of said second conditioned addition into said intermediate result register.

A circuit for producing A×B mod N, where A and B are binary numbers with at least one of them being considered as having m blocks with k bits each and where N is a binary number, said circuit comprising:

• an intermediate storage register;
• a multiplicand register for storing the value of A;
• a constant register for storing the value Rm+1 mod N where R=2k;
• a first multiplier for producing the product of A and Bi where Bi is a k bit block of B with B0 being the low order block;
• a second multiplier for producing the product of the contents of said constant register and the leftmost k bits in said intermediate storage register;
• a first unconditioned adder for producing the sum of the product from said second multiplier and the contents of the rightmost mk bits from said intermediate storage register with k bits, which are zero, appended on the rightmost end of said rightmost mk bits, said first unconditioned adder also producing a first carry signal;
• a first conditioned adder for producing the sum of the contents of said constant register and the sum from said first unconditioned adder upon the condition that said first carry signal indicates a carry out of the leftmost bit position from said first unconditioned adder;
• a second unconditioned adder for producing the sum of the product from said first multiplier and the sum from said first conditioned adder, said second unconditioned adder also producing a second carry signal;
• a second conditioned adder for producing the sum of the contents of said constant register and the sum from said second unconditioned adder upon the condition that said second carry signal indicates a carry out of the leftmost bit position from said second unconditioned adder;
• and
• a feedback connection for supplying the sum from said second conditioned adder to said intermediate storage register.

A computer readable medium having computer executable instructions thereon for causing a computer to perform the following operations for producing A mod N, where A is a binary number considered as having n blocks with k bits each and where N is a binary number considered as having m blocks of k bits each:

• loading the value RN=Rm+1 mod N, where R=2k, into a first register;
• loading a second register for the variable Z with the high order m blocks for A;
• and
• for values of i ranging from n−1 to m+1, replacing the value in said second register with the value Z−ZiRi+ZiRNRi−m−1, but if adding ZiRN and the low order (m+1)k bits of the second register produces a carry out indication, replacing the value in said second register instead with the value Z−ZiRi+ZiRNRi−m−1−Ri+RNRi−m−1, where Z is the current value in said second register and Zi is the high order k bits in said second register, and shifting said second register left and shifting into said second register, on the right thereof, the next k bit block of A.

A computer readable medium having computer executable instructions thereon for causing a computer to perform the following operations for producing A×B mod N, where A and B are binary numbers with at least one of them being considered as having m blocks with k bits each and where N is a binary number considered as having m blocks of k bits each:

• loading a value Rm+1 mod N, where R=2k, into a first register;
• loading A into a multiplicand register;
• setting an intermediate result register to zero;
• for values of i ranging from m−1 to 1 carrying out steps (a) through (g) below:
• (a) forming a first product of A and Bi where Bi is the ith k bit block of B with B0 being the low order block;
• (b) adding, in a first unconditional addition, the contents of said intermediate result register to said first product;
• (c) upon the condition that said first addition produces a carry out, adding, in a first conditional addition, the contents of said first register to the results of said first unconditional addition to produce an output having k high order bits and mk low order bits, otherwise adding zero to produce said output;
• (d) forming a second product of the contents of said first register and the k high order bits from the output of said first conditional addition;
• (e) adding, in a second unconditional addition, the mk low order bits from said first conditional addition with k bits, which are zero, appended on the rightmost end of said mk low order bits, and said second product;
• (f) upon condition that said second unconditional addition produces a carry out, adding, in a second conditional addition, the contents of said first register to the results of said second unconditional addition, otherwise adding zero;
• and
• (g) loading the result of said second unconditional addition operation to said intermediate result register.

A computer readable medium having computer executable instructions thereon for causing a computer to perform the following operations for producing A×B mod N, where A and B are binary numbers with at least one of them being considered as having m blocks with k bits each and where N is a binary number considered as having m blocks of k bits each:

• loading a value Rm+1 mod N, where R=2k, into a first register;
• loading A into a multiplicand register;
• setting an intermediate result register to zero;
• for values of i ranging from m−1 to 0 carrying out steps (a) through (g) below:
• (a) forming a first product of the contents of said first register and the leftmost k bits in said intermediate result register;
• (b) adding, in a first unconditioned addition, said first product and the low order mk bits from said intermediate result register with k bits, which are zero, appended on the rightmost end of said mk bits and;
• (c) upon condition that said first unconditioned addition produces a carry out, adding, in a first conditioned addition, the output from said first unconditioned addition and the contents of said first register, otherwise adding zero;
• (d) forming a second product of the contents of said multiplicand register and Bi where Bi is the ith k bit block of B with B0 being the low order block;
• (e) adding, in a second unconditioned addition, said second product and the output from said first conditioned addition;
• (f) upon condition that said second unconditioned addition produces a carry out, adding, in a second conditioned addition, the output from said second unconditioned addition and the contents of said first register, otherwise adding zero;
• and
• (g) loading the result of said second conditioned addition into said intermediate result register.