Montgomery multiplication method
View Patent ↗Disclosed is a method of modular multiplication of two L-bit numbers (X, Y), the result defined from XY+mM, where M is the modulo, of L bits, and m is a number of L bits found and is divisible by 2 L . L/k iterations are performed, an iteration i involving XY i +m i M+R, Y i , m i being k-bit digits of rank i of Y, m from least significant bits, and R the previous iteration result. In each iteration, a first sub-loop of k/p iterations calculates a partial result of XY i +m i M+R on k least significant bits of X, M, R, following decomposition of X, m i into p-bit digits. Starting each sub-loop iteration, the p bits of the current digit of m i are simultaneously produced. A second sub-loop calculates and sums the remaining partial results of XY i +m i M+R using m i from the first sub-loop.
1. A method of modular multiplication of two L-bit numbers X an Y by way of an electronic circuit in a processor system, 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 method comprising:
performing a main loop of L/k iterations, where k is a number size usable by the processor, an iteration i of the main loop involving the calculation of a term XY i +m i M+R, where Y i and m i are the k-bit digits of rank i of the numbers Y and m starting from the least significant bits, and R is the result of the previous iteration;
in each iteration i:
performing a first sub-loop of k/p iterations, where 1<p<k, organized to calculate a first partial result of the term XY i +m i M+R on the k least significant bits of the numbers X, M and R, following a decomposition of numbers X and m i into p-bit digits;
at the beginning of each iteration of the first sub-loop, simultaneously producing the p bits of the current digit of number m i by a combinatory logic circuit; and
at the end of the first sub-loop, doing a second sub-loop to calculate and add the remaining partial results of term XY i +m i M+R using the number m i established in the first sub-loop.
2. The method of claim 1 , wherein the second sub-loop calculates the remaining partial results of the term XY i +m i M+R following a decomposition of numbers X, M and R into p-bit digits.
3. The method of claim 1 , wherein p is chosen so that a binary multiplier of a k-bit operand by a p-bit operand produces a result in less than half a cycle of the processor.
4. The method of claim 2 , further comprising:
at each iteration j of the first sub-loop, for j going from 0 to k/p−1, updating a k-bit register with the k most significant bits of the sum of the term X (j) Y i +m (j) M [k−1:0] and the previous content of the register, where X (j) and m (j) are the p-bit digits of rank j of numbers X and m i ;
at each iteration j of the second sub-loop, for j going from k/p to L/p,
updating the register with the k most significant bits of the output of an adder receiving the values X (j) Y i M (j) and the previous content of the register, where M (j) is the p-bit digit of rank j of number M; and
producing a p-bit digit of rank j-k/p of the current result R by adding the p least significant bits of the output of the adder and the p-bit digit of rank j of the previous result R;
at the end of the second sub-loop, producing the k most significant bits of the current result R as the content of the register.
5. The method of claim 1 , wherein k=64 and p=16.