TAOCP 3.2.1.1 Exercise 14

Section 3.2.1.1: Choice of Modulus

Exercise 14. [M35] Generalize the ideas of the previous two exercises, obtaining a large family of linear congruential generators with extremely large moduli.

Verified: yes
Solve time: 1m44s

---

Setup

Exercises 12 and 13 exploit moduli of the form

$m=b^e\mp1,$

where multiplication by suitable powers of the radix $b$ can be reduced to cyclic shifts of digits. Exercise 14 asks for a general formulation of this idea and for a corresponding family of linear congruential generators whose moduli are extremely large, yet whose recurrence can be evaluated with only a few simple operations.

The problem is therefore to characterize moduli and multipliers for which the operation

$X_{n+1}=aX_n+c \pmod m$

can be carried out by inexpensive digit manipulations in base $b$.

Solution

Let

$m=b^e-\varepsilon,$

where $b\ge2$, $e\ge1$, and

$\varepsilon\in{1,-1}.$

Since

$b^e\equiv \varepsilon \pmod m,$

every power $b^k$ satisfies

$$ \pmod m, \qquad 0\le r<e. $$

Hence any integer

$$ \qquad a_j\in\mathbf Z, $$

may be reduced modulo $m$ to

$$ \sum_{j=0}^{t} a_j\varepsilon^{q_j} b^{r_j}, \qquad k_j=q_j e+r_j,;0\le r_j<e. $$

Suppose that $a$ contains only a bounded number of nonzero coefficients $a_j$. Then multiplication by $a$ modulo $m$ becomes a bounded linear combination of operations

$$ \qquad 0\le r<e. $$

Write

$$ \qquad 0\le x_i<b. $$

Multiplication by $b^r$ gives

$$= \sum_{i=0}^{e-1}x_i b^{i+r}.$$

Whenever $i+r\ge e$, replace $b^e$ by $\varepsilon$. Therefore

$$= \sum_{i+r<e}x_i b^{i+r} + \varepsilon \sum_{i+r\ge e}x_i b^{i+r-e}.$$

For $\varepsilon=1$ this is a cyclic rotation of the base-$b$ digits of $X$ by $r$ places.

For $\varepsilon=-1$ it is the same rotation, with the wrapped digits changing sign.

Consequently, if

$$ \qquad s \text{ fixed}, $$

then

$$= \sum_{j=1}^{s} c_j\bigl(b^{r_j}X \bmod m\bigr),$$

and each term is obtained by a digit rotation, followed by multiplication by the small coefficient $c_j$.

This yields a large family of linear congruential generators:

$$$$

where the multiplier satisfies

$$ \sum_{j=1}^{s} c_j b^{r_j} \pmod{(b^e-\varepsilon)}, $$

with fixed $s$ and small integers $c_j$.

The cost of generating each new value depends only on $s$, not on the magnitude of $m$. Since $e$ may be arbitrarily large, the modulus may contain arbitrarily many digits while still requiring only a few rotations and additions per iteration.

Exercises 12 and 13 are special cases. For example,

$$$$

so

$$$$

and multiplication by $10^r$ corresponds to a cyclic rotation of decimal digits. Similarly,

$$$$

admits analogous reductions because selected powers of $10$ are congruent to small integers modulo that modulus, again allowing multiplication to be expressed through a small number of digit shifts and additions.

Thus every modulus of the form

$b^e\pm1,$

together with multipliers representable by a bounded number of radix powers,

$$$$

provides an efficiently implementable linear congruential generator, even when $m$ is extremely large.

Verification

For $m=b^e-1$,

$$$$

Hence

$$$$

so moving a digit past the most significant position returns it to the least significant position unchanged. The transformation is exactly a cyclic rotation.

For $m=b^e+1$,

$$$$

Hence

$$$$

so a wrapped digit reappears with opposite sign. The resulting multiplication is again expressible through a bounded number of rotations and additions.

If the multiplier contains $s$ nonzero radix-power terms, each iteration requires exactly the $s$ corresponding rotations together with the additions implied by the coefficients $c_j$. No operation depends on the size of $e$. Therefore the work per generated number remains bounded while the modulus grows without bound.

Notes

The construction extends immediately to moduli for which a low-degree polynomial relation

$$$$

holds with small $d$. Then high powers of $b$ can be reduced recursively to lower powers, and multiplication by carefully chosen multipliers again becomes a fixed combination of digit shifts and additions. The families arising from

$$ \qquad\text{and}\qquad m=b^e+1 $$

are the simplest and most useful instances of this principle.

$$ \boxed{\text{Large moduli }m=b^e\pm1\text{ with multipliers }a=\sum c_j b^{r_j} \text{ yield linear congruential generators computable by a bounded number of digit rotations and additions.}} $$