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 ?