Montgomery Algorithm

Question

I'm trying to understand how it works and how to implement the algorithm described in this paper. The paper shows a methods to compute a modular multiplication where it is used multiplier with a resolution smaller than output resolution. For example if I want to do a modular multiplication with 2 1024 bits numbers I can use 16 bits adders.

I've extracted the algorithm for simplicity :

$ S = 0\\ for\ i=0\ to\ (m-1)\ loop\\ \ \ \ \ (C,S^{(0)}) := x_i\cdot Y^{(0)}+S^{(0)}\\ \ \ \ \ if\ S^{(0)}_{0} = 1\ then\\ \ \ \ \ \ \ \ \ (C,S^{(0)}) := (C,S^{(0)}) + M^{(0)}\\ \ \ \ \ \ \ \ \ for\ j = 1\ to\ e-1\ loop\\ \ \ \ \ \ \ \ \ \ \ \ \ (C,S^{(j)}) := C+ x_i \cdot Y^{(j)} + M^{(j)} + S^{(j)}\\ \ \ \ \ \ \ \ \ \ \ \ \ S^{(j-1)} := (S_0^{(j)},S^{(j-1)}_{w-1..1}) \\ \ \ \ \ \ \ \ \ end\ loop\\ \ \ \ \ \ \ \ \ S^{(e-1)} := (C,S^{(e-1)}_{w-1..1})\\ \ \ \ \ else\\ \ \ \ \ \ \ \ \ for\ j = 1\ to\ e-1\ loop\\ \ \ \ \ \ \ \ \ \ \ \ \ (C,S^{(j)}) := C+ x_i \cdot Y^{(j)} + S^{(j)}\\ \ \ \ \ \ \ \ \ \ \ \ \ S^{(j-1)} := (S_0^{(j)},S^{(j-1)}_{w-1..1}) \\ \ \ \ \ \ \ \ \ end\ loop\\ \ \ \ \ \ \ \ \ S^{(e-1)} := (C,S^{(e-1)}_{w-1..1})\\ \ \ \ \ end\ if\\ end\ loop\\ $

where I have :

• $\\S$ is the result
• $M$ is the module
• $Y$ is the multiplicand
• $X$ is the multiplier and $x_i$ is the single bit (e.g. $X = (x_n,...,x_1,x_0)$.
• The superscript are the words vectors ( e.g. $M = (0,M^{e-1},...,M^1,M^0)$
• $(A,B)$ is the concatenation of two bit vector.
• $m$ is the operands width
• $w$ is the width of chosen words
• $e$ is the number of $w$ bits required to complete the vectors ( $e = \lceil(m+1)/w\rceil$

I don't understand what the authors mean with the variable $C$. It should be the carry, but the problem is that I don't understand what carry they are using, Is the carry of the previous addiction ?

P.S. In the paper it's written that $C$ is in the range $[0,2]$ . Thus, $C$ is represented by 2 bits. The problem is that in the algorithm there is this step :

$S^{e-1} := (C,S^{e-1}_{w-1..1})$

It represents the concatenation of :

• $C$ : $2$ bits.
• $S^{e-1}_{w-1..1}$ : $w - 1$ bits.

So the concatenation is $w + 1$ bits and it shouldn't be possible. Where is my mistake ?

Answer 1

The confusion comes from the choice of representation. I'd a quick look to the referenced paper, where the autors use a 2-radix representation. Then you shoud initialise $e=\frac{m+15}{w}$ instead of $e=\frac{m+1}{w}$ as you use a 16 bit adder! The best is to read again the seminal paper of P.L. Montgomery:http://web.itu.edu.tr/~orssi/dersler/cryptography/Montgomery.pdf

ANd this remak explain the additionnal word set to ZERO in the modulus.

The method introduced by Montgomery is clever and require a change or representation as explained in the paper. the method allows also to overlap mul and ReduC process. I confirm also than C represent the carry which require 2 bits to be holded. The interest compared to the classical method, is that carry propagation is moving from right to left, exactly of the direction of scanning operand. This is the reason why the Mult-ReduC can be overlapped, and which is of great importance in hardware design.

Answer 2

@haster8558 I know this is late, but I am struggling with the same problem. I do have a few answers for you though...

I dont understand why I the number of the word are linked to the width of the adders

They aren't. I believe Robert NACIRI is wrong on this one. The number of words is only linked to the number of DIGITS (bits if you are in base 2, decimal digits if you are in base 10) used to represent the parameters (modulus, and multiplier/multiplicand.). The reason that the number of words is defined as $e = \lceil(m+1)/w\rceil$ is because you need an additional word to handle the spillover from the last carry. The width of the adder doesn't have anything to do with the number of words required, but the width of the adder must be influenced by the radix used. However, since most hardware adders are radix-2, this is irrelevant and the given formula for e in the paper will always hold.

If you were using a different radix, you would indeed have a different formula. But this would be grossly inefficient in hardware as you lose the ability to shift instead of divide when using MM for modular exponentiation.