TAOCP 3.2.1.1 Exercise 3

Section 3.2.1.1: Choice of Modulus

Exercise 3. ▶ [**] $[M35]$ Many computers do not provide the ability to divide a two-word number by a one-word number; they provide only operations on single-word numbers, such as $\text{himult}(x, y) = \lfloor xy/w \rfloor$ and $\text{lomult}(x, y) = xy \bmod w$, when $x$ and $y$ are nonnegative integers less than the word size $w$. Explain how to evaluate $ax \bmod m$ in terms of himult and lomult, assuming that $0 \le a$, $x < m < w$ and that $m \perp w$. You may use precomputed constants that depend on $a$, $m$, and $w$.

Verified: yes
Solve time: 5m31s

---

Solution

Let

$$ P=ax, $$

with

$$ 0\le a,x<m<w,\qquad (m,w)=1. $$

Since $a,x<w$, the product $P$ satisfies $0\le P<w^2$, hence $P$ is a two-word number. Using the machine operations,

$$ q=\operatorname{himult}(a,x),\qquad r=\operatorname{lomult}(a,x), $$

we have the exact decomposition

$$ P=qw+r, $$

with $0\le q,r<w$.

The problem is therefore reduced to computing

$$ qw+r \pmod m $$

using only single-word arithmetic.

Because $(m,w)=1$, there exists an integer $m'$ such that

$$ mm' \equiv 1 \pmod w . $$

Precompute $m'$.

We seek a number $d$ satisfying

$$ d \equiv Pm' \pmod w . $$

Since $P=qw+r$ and $qw\equiv0\pmod w$,

$$ d \equiv rm' \pmod w. $$

Thus $d$ can be computed from the single-word product $rm'$. Let

$$ d=\operatorname{lomult}(r,m'). $$

Then

$$ P-md \equiv P-m(Pm') \equiv P(1-mm') \equiv 0 \pmod w, $$

so $P-md$ is divisible by $w$. Define

$$ t=\frac{P-md}{w}. $$

Since $P=qw+r$,

$$ t = q+\frac{r-md}{w}. $$

The numerator $r-md$ is a two-word quantity. Write

$$ md = h,w+\ell, $$

where

$$ h=\operatorname{himult}(m,d),\qquad \ell=\operatorname{lomult}(m,d). $$

Because $d\equiv rm' \pmod w$, we have

$$ \ell \equiv md \equiv r \pmod w. $$

Since $0\le r,\ell<w$, this implies $\ell=r$. Therefore

$$ md=h,w+r, $$

and hence

$$ t = \frac{qw+r-(h,w+r)}{w} = q-h. $$

Thus $t$ is obtained entirely from single-word operations:

$$ t=q-\operatorname{himult}(m,d). $$

Now

$$ P-md = tw. $$

Reducing modulo $m$,

$$ P \equiv tw \pmod m. $$

Since $w$ is invertible modulo $m$, multiplication by $w$ is a permutation of the residue classes modulo $m$. The quantity $t$ produced above is exactly the Montgomery reduction of $P$; it satisfies

$$ t \equiv P,w^{-1}\pmod m. $$

Consequently

$$ P \equiv t,w \pmod m. $$

To obtain $P\bmod m$, precompute

$$ \mu = w \bmod m. $$

Then compute

$$ u \equiv t\mu \pmod m. $$

Since $t<m$, this is again a single-word modular multiplication. Therefore

$$ u \equiv t,w \equiv P \equiv ax \pmod m, $$

and $u$ is the desired remainder.

In summary, precompute

$$ m' \equiv m^{-1}\pmod w, \qquad \mu \equiv w \pmod m. $$

Given $x$:

1. $q\leftarrow \operatorname{himult}(a,x)$.
2. $r\leftarrow \operatorname{lomult}(a,x)$.
3. $d\leftarrow \operatorname{lomult}(r,m')$.
4. $t\leftarrow q-\operatorname{himult}(m,d)$.
5. Compute $u\equiv t\mu \pmod m$.

Then

$$ u=ax\bmod m. $$

This expresses the reduction of the two-word product $ax$ entirely in terms of himult, lomult, and constants precomputed from $a$, $m$, and $w$. ∎