Exercise 2.4.21* (Modular product)

Proof. We reformulate the algorithm:

1.

Set $k\leftarrow b,c\leftarrow 0,g\leftarrow \lfloor X∕m\rfloor$.

2.

While $a>0$,

(a)

$r=a\%g$.

(b)

$s=(\mathit{kr})\%m$.

(c)

$c\leftarrow c+s$.

(d)

If $c\ge m$, $c\leftarrow c-m$.

(e)

$k\leftarrow (\mathit{gk})\%m$.

(f)

$a\leftarrow \lfloor a∕g\rfloor$.

With python:

     def modular_product(a, b, m, X):
         k, c, g = b, 0, X // m
         while a>0:
             r = a % g
             s = (k * r) % m
             c = c + s
             if c >= m: c = c - m
             k = (g * k) % m
             a = a // g
         return c

Now we explain the algorithm. Note that $g=\lfloor X∕m\rfloor \ge 2$ does not change during the execution of the algorithm. We interpret $g$ as the base of the system of numeration, so that

where $M$ is the numbers of digits in base $g$, and $0\le r_i<g$.

Then

where $k_i\equiv g^{i}b(\mathit{mod}m),0\le k_i<m$ (that is $k_i=(g^{i}b)\%m$).

Define $s_i=(k_i{r}_i)\%m$, and $a_i=\lfloor a∕g^i\rfloor ={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{j=i}^{M-1}{r}_j{g}^j$ for $i=0,1,\dots ,M-1$.

Now we verify that $r_i,a_i,k_i$ are the actual values the parameters $r,a,k$ at the $i$-th passing in the loop (the first passing has index $0$), if we test these values after the step (d).

The rightmost digits of $a$ is $r_0=a\%g$, the remainder of $a$ by $g$. To obtain the following digits, we replace $a$ by $\lfloor a∕g\rfloor ,\lfloor a∕g^2\rfloor ,\dots$. This gives the well known algorithm to decompose a positive integer in the base $g$:

This corresponds to the steps (a) and (f) in the loop, so $r_i$ and $a_i$ are the actual values of $r$ and $a$ in the loop. Moreover, step (e) gives $k_i=(g^{i}b)\%m$.

At each passing of the loop, $c_i\equiv c_{i-1}+s_i(\mathit{mod}m)$, so that $c_i\equiv {\sum <!--\; FUNCTION\; APPLICATION\; -->}_{j=0}^i{r}_j{k}_j(modm)$, and when $a_M=0$, $c=c_M\equiv {\sum <!--\; FUNCTION\; APPLICATION\; -->}_{j=0}^{M-1}{r}_j{k}_j\equiv \mathit{ab}(modm)$.

We prove by induction that $a_i,k_i,c_i$ are in the interval $[0,m[$.

$0\le a_0=a<m,0=k_0=b<m,c_0=0$, so the property is true for $i=0$.

Assume that $0\le a_{i-1}<m,0\le k_{i-1}<m,0\le c_{i-1}<m$. Then $s_i=(k_i{r}_i)\%m<m$, so $0\le c_{i-1}+s_i<2m$. Therefore, after the instruction (d), $0\le c_i<m$. Moreover $0\le k_i=(g^{i}b)\%m<m$, and $a_i=\lfloor a_{i-1}∕g\rfloor <a_{I-1}<m$. The induction is done.

Finally, $0\le r_i<g$, and $0\le k_i<m$, therefore $0\le k_i{r}_i<\mathit{gm}\le X$, since $g=\lfloor X∕m\rfloor$ satisfies $g\le X∕m$. Similarly, $0\le g{k}_i<\mathit{gm}\le X$, so all numbers encountered lie in the interval $[0,X[$.

Since at the end $0\le c<m$, and $c\equiv \mathit{ab}(\mathit{mod}m)$, the result $c$ is the waited result. □