Montgomery Algorithm 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 ?
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.