Montgomery multiplication circuit

1. A circuit for calculating a sum of two products, each product having a q-bit binary operand and a k-bit binary operand, where k is a multiple of q, the circuit comprising:

a q-input Carry-Save Adder;

a multiplexer for each input of the adder, having four k-bit channels respectively receiving the value 0, a first of the k-bit operands, the second k-bit operand, and the sum of the two k-bit operands, wherein the output of a multiplexer of rank t (where t is between 0 and q−1) is taken into account by the adder with a t-bit left shift, and

each multiplexer having first and second channel selection inputs, the bits of a first of the q-bit operands being respectively supplied to the first selection inputs, and the bits of the second q-bit operand being respectively supplied to the second selection inputs.

2. The circuit of claim 1 , wherein the carry-save adder comprises two additional k-bit inputs and supplies a dual output in the form of a partial sum and carry sequence, representing a (k+q)-bit result, the circuit further comprising:

a k-bit register connected to store the k most significant bits of the output of the adder in the form of a partial sum and carry sequence, the content of the register being supplied to the two additional inputs of the adder;

a clock connected to trigger the update of the register; and

a control circuit connected to apply a new pair of q-bit operands to the selection inputs of the multiplexers at each clock cycle.

3. A circuit comprising a plurality of calculation circuits according to claim 1 connected in a chain, wherein:

each carry-save adder comprises two additional inputs and supplies a dual output in the form of a partial sum and carry sequence, representing a (k+q)-bit result;

the k most significant bits of an adder of the chain are supplied, in the form of a partial sum and carry sequence, to the two additional inputs of the next adder of the chain;

the selection inputs of the set of multiplexers of each adder receive a different pair of q-bit operands;

a k-bit register is connected to store the k most significant bits of the output of the last adder of the chain in the form of a partial sum and carry sequence, the content of the register being supplied to the two additional inputs of the first adder of the chain;

a clock is connected to trigger the update of the register; and

a control circuit is connected to apply a new pair of q-bit operands to the selection inputs of each set of multiplexers at each clock cycle.

4. The circuit of claim 3 , further comprising:

a memory location containing a result being calculated; and

a complete adder for each carry-save adder, receiving on a first input bits representative of the q least significant bits of the output of the carry-save adder, receiving on a second input q bits from a first position of the memory location (R), and the output of the complete adder producing q bits written in a second position of the memory location.

5. The circuit of claim 4 , further comprising registers connected to receive operands from an external memory, the frequency of said clock being chosen at twice the frequency of a clock which clocks the accesses to the external memory, said memory location being an internal memory.

6. The circuit of claim 1 , applied to the modular product calculation of two L-bit numbers X and Y, wherein the result of the modular multiplication may be defined from a value XY+mM, where M is the modulo, of L bits, and m is an L-bit number found such that this value is divisible by 2 L , the circuit being used for the calculation of an intermediate term XY i +m i M+R by iterations at the rhythm of a clock, where Y i and m i are the k-bit digits of rank i of numbers Y and m starting from the least significant bits, and R is the sum of the previous terms, the circuit having a first mode where it receives as k-bit operands the number Y i and the k first bits of number M, and as q-bit operands, q bits of number X and q bits of number m i , the circuit further comprising:

a control circuit arranged to select as q-bit operands, at each iteration, a different pair of q-bit packets of the numbers X and mi;

a combinatory logic circuit supplying at each iteration the current q-bit packet of number mi;

a first register receiving in juxtaposition the q-bit packets of number mi; and

a second register containing a k-bit value representative of the previous iteration, supplied to two additional inputs of the carry-save adder in the form of a partial sum and carry sequence.

7. The circuit of claim 6 , having a second mode where it receives as k-bit operands the number Y i and the number m i contained in the first register, and as q-bit operands, q bits of the numbers X and M, the control circuit being arranged to select as q-bit operands, at each iteration, a different pair of q-bit packets of the numbers X and M.

8. The circuit of claim 1 , wherein q=4 and k=64.